Prime Numbers

[gregv21]

Does anyone have any ideas on how to make a program that check if a number is prime

[yang]

let the number divided by all the primes from 2 to the square of itself

[magicalblender]

Yang has a good idea. Let me elaborate.
A number is prime if it is not evenly divisible by any number other than itself and 1.
So, if you check every number from 2 to N, and none of them divide into N, then N is prime.
You can further optimize this by only checking from 2 to the square root of N. Now, I don't exactly understand why this is true, but it's based on very sound mathematical reasoning, so let's just accept it.

boolean is_it_prime(int N){
   for(int i = 2; i <= sqrt(N); i++){
      if ((N % i) == 0){return false;}  //divides evenly- NOT PRIME!
   }
   return true;   //no numbers divided evenly- PRIME!
}

If you're trying to find the primeness of a whole lot of numbers all in a row, it may be much more efficient to use a prime sieve.
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

[Hotaru]

Depending upon your application, perhaps you can use common divisibility rules to exclude a number as prime.

Even numbers are not prime.
If last digit is 5, not prime (divisible by 5).
If sum of digits is divisible by 3, number is divisible by 3 and not prime.

[z05DSL3A]

"Even numbers are not prime."

2 is prime and even. :0)

[gregv21]

thanks i got it now

[tomao]

boolean is_it_prime(int N){
   for(int i = 2; i <= sqrt(N); i++){
      if ((N % i) == 0){return false;}  //divides evenly- NOT PRIME!
   }
   return true;   //no numbers divided evenly- PRIME!
}

shouldn't you use 'bool' when declaring the function? I have never heard of declaring with 'boolean'.

[magicalblender]

I guess so. I don't know what I was thinking when I wrote that.