CODEWITHSUNDEEP
c++loopsprimes
J. Doe
J. Doe

Reputation: 21

Loop not faster despite looping through half as many iterations?

I wrote a program that searches for primes:

#include <iostream>
#include <fstream>
#include <chrono>

typedef std::chrono::high_resolution_clock Clock;
using namespace std;

int main() {
    int p;
    int x = 1;
    int b;
    int a[1000000];
    bool n = false;
    a[0] = 2;
    a[1] = 3;

    auto t1 = Clock::now();

    ofstream outfile;
    outfile.open("p.txt");

    for (p = 3; p < 7500000; p = p + 2)
    {
        for (b = 0; b <= x && n == 0; b++)
        {
            if (p % a[b / 2] == 0)
            {
                n = true;
            }
        }
        if (n == false)
        {
            cout << p << endl;
            outfile << p << endl;
            x++;
            a[x] = p;
        }
        else
        {
            n = false;
        }
    }

    auto t2 = Clock::now();
    std::cout
        << std::chrono::duration_cast<std::chrono::nanoseconds>(t2 - t1).count()
        << " nanoseconds" << std::endl;
    outfile.close();
}

Initially for the loop increment I had p++, but I changed that to p=p+2 because all primes essentially are odd and even numbers don't need to be checked. Problem is when I benchmarked this, there was no difference in speed between the old and new code. So what is the bottleneck in the process, if checking all the numbers is no different than checking half? And is there a better way to approach this?

Upvotes: 1

Views: 79

Answers (2)

The Vee
The Vee

Reputation: 11580

It's this line:

for(b=0; b<=x && n==0; b++)

Once n=true; executes, the b loop exits because of the && n==0 condition. This happens with the very first test: every even number is divisible by two, which is a[0]. So for even numbers (that you include if you use p++ instead of p=p+2) the inner loop is very quick, much quicker than for a typical odd number. This explains why including them makes so little difference.

Upvotes: 0

David Schwartz
David Schwartz

Reputation: 182893

Your outer loop skips half the numbers. But your inner loop tests every number twice. So you give up all your gains.

If you don't see that your inner loop does everything twice, consider that a[b/2] is the same when b is 1 as it is when b is 0.

Upvotes: 1

Related Questions