6.29 C++ How to Program (8th Edition) By Paul Deitel, Harvey Deitel

(Prime Numbers) An integer is said to be prime if it’s divisible by only 1 and itself. For example, 2, 3, 5 and 7 are prime, but 4, 6, 8 and 9 are not.

a) Write a function that determines whether a number is prime.

b) Use this function in a program that determines and prints all the prime numbers between 2 and 10,000. How many of these numbers do you really have to test before being sure that you’ve found all the primes?

c) Initially, you might think that n/2 is the upper limit for which you must test to see whether a number is prime, but you need only go as high as the square root of n. Why? Rewrite the program, and run it both ways. Estimate the performance improvement.
Solution:

a)

#include <iostream>
using std::cout;
using std::cin;
using std::endl;
 
void primeNumber(int);
 
int main()
{
   int i;
 
   cout << "Enter integer: ";
   cin >> i;
   primeNumber(i);
 
   return 0;
}
void primeNumber(int i)
{
   int prime = 0;
   for(int j = 2; j < i; j++)
   {
      if(i % j == 0)
         prime++;
 
   }
   if(prime > 0)
      cout << "The integer is not prime";
   else
      cout << "The integer is prime";
}
 
 

b) We can exclude even numbers and test half of numbers.

 
// comments
 
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
 
int primeNumber(int);
 
int main()
{
   for(int x = 1; x <= 10000; x += 2)
   {
      if( x == primeNumber(x))
         cout << x << endl;
   }
 
   return 0;
}
int primeNumber(int x)
{
   int prime = 0;
 
   for(int j = 2; j < x; j++)
   {
      if(x % j == 0)
         prime++;
 
   }
   if(prime == 0)
      return x;
}
 
 

c) If the number is not prime, it can be represented by two divisors. For example, 9 = 3 * 3 or 8 = 2 * 4. The smaller divisor always equal or less than square root of number. if the number is divisible by an integer greater than the square root of that number, it must be divisible by the quotient of this division, which is clearly smaller than the square root.

 
 
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
 
#include <cmath>
 
int primeNumber(int);
 
int main()
{
   for(int x = 1; x <= 100000; x += 2)
   {
      if( x == primeNumber(x))
         cout << x << endl;
   }
 
   return 0;
}
int primeNumber(int x)
{
   int prime = 0;
 
   for(int j = 2; j < sqrt(x); j++)
   {
      if(x % j == 0)
         prime++;
 
   }
   if(prime == 0)
      return x;
}
 
 

Performance for x <= 100000:

b)
Process returned 0 (0x0) execution time : 23.094 s
Press any key to continue.

c)
Process returned 0 (0x0) execution time : 1.797 s
Press any key to continue.