cplusplus.com
C++ : Forum : Beginners : Prime Numbers
 
cplusplus.com
Information
Documentation
Reference
Articles
Forum
Forum
Beginners
Windows Programming
UNIX/Linux Programming
General C++ Programming
Lounge
Jobs


question Prime Numbers

gregv21 (50)
Does anyone have any ideas on how to make a program that check if a number is prime
Last edited on
yang (33)
let the number divided by all the primes from 2 to the square of itself
magicalblender (92)
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)
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 (2845)
"Even numbers are not prime."

2 is prime and even. :0)
gregv21 (50)
thanks i got it now
tomao (31)
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 (92)
I guess so. I don't know what I was thinking when I wrote that.
Topic archived. No new replies allowed.