Counting prime numbers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
    #include <iostream>
    using std::cout;
    using std::cin;
    using std::endl;

    int main()
    {
       int maxN;
       cout << "Enter the largest number to test:";
       cin >> maxN;

       unsigned int primeCount = 0;
       for(int i = 2; i <= maxN; i++ /*shorter than i = i + 1*/)
       {
          if(i == 2)
          {
             primeCount++; // 2 is a prime;
             continue; // test next value
          }
          else if(!(i % 2))
          {
             continue; // it is even, so skip the testing, its not prime
          }
          bool isPrime = true; // to see if it ends up prime
          for(int j = 3 /*next value to test*/ ; j < maxN / 2 /*factor will always be < num / 2*/; j += 2 /*since we already tested evens*/)
          {
             if(!(i % j)) // i is evenly divided by j
             {
                isPrime = false; // it isnt prime
                break; // start w/ next number
             }
          }
          if(isPrime) // we had a prime last time through
             primeCount++; // increment the counter
       }

       cout << "\n\nThere are " << primeCount << " prime numbers up to " << maxN << ".";

       return 0;
    }
You have the right idea. You can speed it up by lowering the loop limit at line 25 to sqrt(I). Store this value in a variable first. Otherwise it will be recalculated each time through the loop and that takes a lot of time.

You could also start primecount at one and run the loop from 3, and incrementing by 2, but that is a small savings, and your will hav you would have to add coffee for when maxN <2.
Topic archived. No new replies allowed.