# about counting prime numbers

Printable View

• 10-27-2003
cengiz
about counting prime numbers
#include <iostream>
using namespace std;
int main(void)

{
cout << "Input the largest positive integer to check: ";
unsigned int maxN;
cin >> maxN;

unsigned int nPrimes =0;

for (int i = 2; i <=maxN; i =i + 1)
{
bool isPrime =true;
for (int j =2; j < i; j =j + 1)
{
if (i%j ==0) isPrime =false;
}
if (isPrime)
{ // cout << i << " "; //Use to check that you’re getting primes

nPrimes =nPrimes + 1;
}
}
cout << "\n\nThere are " << nPrimes << " prime numbers <=" << maxN << endl;

return 0;
Code:

`#include <iostream>`
• 10-27-2003
cengiz
the code above
Hi,
I'm pretty new with c++ and have a question about coding a program that counts the prime numbers in a range of 2 to 100000. Actually I have a code written above but it counts the prime numbers very slowly. It takes about 130 seconds for the program to count the prime numbers up to 100000. How can I make it faster? Should I use vectors? I should get this code working about more than 5000 times faster. I appreciate your help, thanks....
• 10-28-2003
gustavosserra
You do not need to test the number N until N-1. I mean, the square of the number is a good limit:
Code:

```int main() {   for(int i=1;i<100000;i++)   {       bool prime = true;       if( i%2!=0){         float limit = sqrt(i);         for(j=3;j<limit && prime;j+=2){             if( i%j==0 ) prime = false;         }       }       else prime = false;       if( prime ) cout << i << "is prime" << endl; }```