question  Prime Numbers

gregv21 (47)   Link to this post
Does anyone have any ideas on how to make a program that check if a number is prime
Last edited on
yang (33)   Link to this post
let the number divided by all the primes from 2 to the square of itself
magicalblender (82)   Link to this post
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.

1
2
3
4
5
6
 
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
Last edited on
Hotaru (31)   Link to this post
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.
Grey Wolf (1407)   Link to this post
"Even numbers are not prime."

2 is prime and even. :0)
gregv21 (47)   Link to this post
thanks i got it now
tomao (31)   Link to this post
1
2
3
4
5
6
 
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 (82)   Link to this post
I guess so. I don't know what I was thinking when I wrote that.

This topic is archived - New replies not allowed.