I have assignment and need help determining if I am correct. The question reads:

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

b.use the function to determine and print out all prime numbers between 2 and 10,000. **How many numbers to you have to test before being sure that you have found all primes?**

c. You might think 2/n is the upper limit for the test, but you need to go as high as the square root of n. **Why?** Rewrite the program and estimate the performance improvement.

So the bold is the areas I need direction in.

First using 2/n

```
#include <iostream>
using std::cout;
using std::endl;
using std::cin;
#include <cmath>
#include<iomanip>
using std::setw;
bool prime(int n);
int main()
{
int count = 0;
cout << "The prime numbers from 2 to 10000 are:\n";
for (int x =2; x <= 10000; ++x )
if (prime(x))
{
++count;
cout << setw( 6 ) << x;
if ( count % 5 == 0)
cout << endl;
}
cout << "\nThere were " << count << " prime numbers tested\n" << endl;
return 0;
}
bool prime (int n)
{
for ( int z = 2; (n/2) + 1 > z; z++ )
if( n%z == 0 )
return false;
return true;
}
```

Second using sqrt(n)

```
#include <iostream>
using std::cout;
using std::endl;
using std::cin;
#include <cmath>
#include<iomanip>
using std::setw;
bool prime(int n);
int main()
{
int count = 0;
cout << "The prime numbers from 2 to 10000 are:\n";
for (int x =2; x <= 10000; ++x )
if (prime(x))
{
++count;
cout << setw( 6 ) << x;
if ( count % 5 == 0)
cout << endl;
}
cout << "\nThere were " << count << " prime numbers tested\n" << endl;
return 0;
}
bool prime (int n)
{
for ( int z = 2; z<=sqrt(double(n)); z++)
if( n%z == 0 )
return false;
return true;
}
```

So thoughts, comments, ideas??

M