> 1. I'm not sure what the difference is between forward iterators and input iterators.
> Isn't forward iterator the most generic iterator ? I'll have to refresh my c++ knowledge.

The read-only iterator hierarchy goes: input, forward, bidi, random. Input iterators are single-pass iterators, which means that this does NOT work for them:

InIt i = ...; // get i from somewhere
Val v1 = *i; // get a value from i
InIt old = i; // copy i, this is OK so far but bogus code is imminent
++i; // increment i, still OK so far, but old is now UNUSABLE
Val v2 = *old; // FORBIDDEN!!!

The best example of an input iterator is istream_iterator. As you read values, they're consumed from the stream, so you can't go back and replay them.

Forward iterators are multi-pass iterators, merely constrained to go forwards and never backwards. The best example of a forward iterator is forward_list::iterator (i.e. a singly-linked list).

> I based move_if on how remove_if works.

Ah, that wasn't clear to me. Your new implementation is much better; here are some notes:

5. Your (first == last) check is unnecessary. When an algorithm is inherently correct for empty ranges, you should let it automatically work.

6. You don't actually need new_end - you can use first instead.

7. is_prime is really is_even!

8. count_if() followed by move_if() performs 2N tests. Instead, move_if() to back_inserter() would perform N tests. (In that case, the destination n should start out empty.) If you're concerned about reallocation overhead (which usually isn't a big deal), you can say n.reserve(v.size());.

9. print_vec_int should take const vector<int>&.

10. But at the same time, there's no reason to take const int&.

> Your suggestion of using make_move_iterator() with copy_if() while the moving works it doesn't fix up the input container.

Yes, that was intentional. If I wasn't too concerned about consuming a little extra space, I would use partition_copy() with make_move_iterator() and back_inserter() to 2 output vectors, then swap one of the outputs with the input.