about counting prime numbers

**cengiz** · 10-27-2003

#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>

**cengiz** · 10-27-2003

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....

**gustavosserra** · 10-28-2003

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;
}

Thread: about counting prime numbers

Thread Tools

Search Thread

Display

about counting prime numbers

the code above

Similar Threads

prime number program with function

Counting Numbers in Array, not counting last number!

prime numbers code compile error

writing a program that gives prime factorization of numbers above0