We can check if a number is prime by checking whether any number between 1 and itself divides it evenly (i.e., resulting in a whole number). For example, 7 is prime. We can prove that by noting that:
Now, we're programmers; so, there's a better way we can express this. What we really want to know is whether there's a remainder when we divide 7 by various numbers. If there is, 7 isn't divisible by those numbers. In other words, we want to check the value of 7 modulo some numbers:
Now, one last thing. We can prove a number is prime by checking to make sure that it's not divisible by anything between 2 and the number minus one. But, is that really necessary? For example, 24 is divisible by 12.. but we would already have found out that 24 was composite well before we reached 12 because 24 is also divisible by 2 (2 * 12 == 24). So, we don't really have to check 12 to know whether 24 is prime. In general, just how many numbers do we have to check?
As it turns out, we only have to check up to the square root of the number. So, to prove 7 is prime, we need only know that it's not divisible by 2. To check that 11 is prime, we need only know that it's not divisible by 2 or 3. To check whether 10001 is prime, we need only check whether it is divisible by any number from 2 up to 100.
Remember that you can use the function sqrt from the
math.h library to find the square root of a number.
That should be enough information to get you up and running testing for primality. Good luck!