An integer is said to be prime if it’s divisible by only 1 and itself. For ex- ample, 2, 3, 5 and 7 are prime, but 4, 6, 8 and 9 are not.

Question

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.

Answer 1

If a number n has two factors a and b, then one must be less than the square root of n and one must be greater. Therefore, if n is not prime it will have at least one factor less than the square root of n, and we only need to check that far. The performance improvement is roughly a factor of ten, though the running times are so small they are difficult to measure.

```
// Testing for prime numbers.
#include
#include
using namespace std;

bool isPrime( int ); // function prototype

int main()
{
int count = 1; // total number of primes found

cout << "The prime numbers from 1 to 10000 are:" << endl;
cout << setw( 6 ) << 2; // 2 is only even prime

// loop through odd numbers; even numbers > 2 cannot be prime
for ( int loop = 3; loop < 10000; loop += 2 )
{
if ( isPrime( loop ) ) // if current number prime
{
count++;
cout << setw( 6 ) << loop;

if ( count % 10 == 0 ) // new line after 10 values displayed
cout << '\n';
} // end if
} // end for

cout << endl << "Total of " << count
<< " prime numbers between 1 and 10000." << endl;
} // end main
// isPrime returns true if n is prime
bool isPrime( int n )
{
// loop through possible factors
for ( int loop2 = 2; loop2 <= n / 2; loop2++ )
{
// if factor found, not prime
if ( n % loop2 == 0 )
return false;
} // end for

return true;
} // end function isPrime
```