prime number (idea)

The following was in response to rabidcow's first two paragraphs only; it is not a criticism of the C program added afterwards.

Um, I don't think that is as helpful as it would like to be. How do you know something is a multiple of 6? It has to be (a) a multiple of 2; (b) a multiple of 3.

To check (a) look at the last digit; to check (b) add up all the digits (repeatedly if necessary) to see whether their sum is divisible by 3. Both simple operations.

But any number is precisely one of

1. a multiple of 6
2. 1 more than a multiple of 6
3. 2 more than a multiple of 6
4. 3 more than a multiple of 6
5. 4 more than a multiple of 6
6. 5 more than a multiple of 6

These can be checked with

1. either (a) or (b), but (a) is easier
2. neither
3. (a)
4. (b)
5. (a)
6. neither

Being 5 more than is the same as being 1 less than (modulo 6), so this leaves the two possibilities rabidcow mentioned. But in no case do you have to do the (relatively) hard work of checking both (a) and (b). The o(1) algorithm (a) eliminates half and the o(n) algorithm (b) eliminates a further one-sixth.

If it's still a candidate after this you have to do work, but its passing these tests has incidentally told you that it's a multiple of 6, plus or minus 1, a converse of the previous write-up's idea.