Prime numbers list
List of prime numbers
Write a C++ program to find the prime numbers between 100 and 10000
What is a prime number
Definition: A number (N) is prime if it has no divisors except 1 and (N)
Prime number calculator
To check if (N) is prime we divide (N) by all numbers from 3 to (N-1) one at a time. If we can find at least one number that divides (N) then (N) is not a prime otherwise it is a prime number. This technique is good for small numbers but it becomes impractical for large numbers. For example if we want to check whether (1000) is a prime number or not then we need to check if it can be divided by any number between (3) and (999). There are some fast primality tests that require advanced mathematics however we can improve the algorithm described earlier a little bit if we notice that all of the divisors of a number come in pairs for example (24) has the following divisors: (1,24) (2,12) (3,8) (4,6). The key is to notice that all of the first numbers occur before the square root of (24). In other words, if a number (N) has a divisor greater than (1) it must be less than or equal to the square root of (N). So you just need to try all the numbers from (3) up to the square root of (N). As you can see the square root of (N) is way less than N which reduces the number of iterations dramatically. Notice that we start at (3) not at (2) because if the number is even and greater than (2) it can not be prime. Moreover testing for divisors from (3) to the square root of (N) need not to include even divisors. This would even improve the performance of the algorithm a little bit more and finally if a divisor is found then there is no need to continue testing the other divisors.
Prime number sequence code
Here is a C++ code example algorithm to do that
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
//Includes #include <iostream> using namespace std; //Main program void main() { //Loop through the numbers 100 and 10000 //Note that even numbers are skipped //If you start the loop at 100 you will get //wrong results because we are incrementing //(n) by 2 every iteration. for (int n = 101; n < 10000; n+=2) { //p = 1 means prime //P = 0 means not prime int p = 1; //Find square root of N then //cast to the nearest integer int s = (int) std::sqrtf(n); //Try to find a divisor of N //note that even divisors are //skipped for (int d = 3; d <= s; d+=2) { //If the remainder is 0 then it is a divisor //in other words it is not a prime number if (n%d == 0) { p = 0; //Once you find one divisor no //need to continue testing the others break; } } if (p == 1) cout << n << " is prime" << endl; } } |
I hope we got prime numbers explained in this short tutorial. If you have questions or comments, please use the comments section below. Thanks for visiting.
About Author
Mohammed Abualrob
Software Engineer @ Cisco