Prime generator from one to n

Question

My code calculates primes from one to n. I have verified that the code always produces all the primes in that range correctly.

Are there any optimizations that I can make? Are there any bad programming practices besides variable names (e.g. l is close to 1)? Any better normal Windows API? I am using the Sieve of Eratosthenes.

#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <Windows.h>

using namespace std;

#define printprimes() //for each(bool b in primes) cout << b << endl;

int main(int argc, char* argv[])
{
    const double s = GetTickCount();
    unsigned long long numt;
    if(argc < 2) {
        cout << "Usage: "<<argv[0]<<" <primes until...>" << endl;
        return 1;
    }

    else if(atoi(argv[1])<1) {
        cout << "Usage: "<<argv[0]<<" <primes until...>" << endl;
        return 1;
    }
    numt = atol(argv[1])+1;

    bool skipprint = false;

    if(argc >=3) if(!strcmp(argv[2], "noprint")) skipprint = true;

    vector<bool> primes(numt);

    primes.assign(numt, true);

    primes[0] = false;
    primes[1] = false;

    long double sqrtt = sqrt(numt);
    for(unsigned long long l = 0; l<=sqrtt; l++) {
        if(!primes[l]) {
            //cout << l << " is false" << endl;
            continue;
        }
        for(unsigned long long cl = 2*l; cl < numt; cl+= l) {
            //cout << cl << ", a multiple of " << l << endl;
            primes[cl] = false;
        }
    }
    const double m = GetTickCount();
    unsigned long long count = 0;
    if(!skipprint) for(unsigned long long l = 0; l<numt; l++) if(primes[l]) {
        cout << l << endl;
        count ++;
    }
    if(skipprint) for(unsigned long long l = 0; l<numt; l++) if(primes[l]) count ++;
    const double e = GetTickCount();
    cout << endl;
    cout << count << " primes less than or equal to " << numt-1 << endl;
    cout << "Calculation took " << m-s << " ms";
    if(!skipprint) cout << " and printing took " << e-m << " ms";
    else cout << " and counting took " << e-m << " ms";
    cout <<"." << endl;
    //for each(bool b in primes) cout << b << endl;

    return 0;
}

Answer 1

The algorithm looks good overall. Here are a few comments :

---

using namespace std; is sometimes frowned upon : some might say that putting it in a cpp file (by opposition to a header file) is ok, some might say that it's not. In any case, it is worth having a read at the link.

---

#define printprimes() //for each(bool b in primes) cout << b << endl;

does not seem really useful.

---

If you want to handle wrong input in a better way you could have a look at the other ways to convert arrays of char to number.

---

bool skipprint = false;

if(argc >=3) if(!strcmp(argv[2], "noprint")) skipprint = true;

can become :

bool skipprint = false;
if(argc >=3 && !strcmp(argv[2], "noprint")) skipprint = true;

which is nothing but :

bool skipprint = (argc >=3 && !strcmp(argv[2], "noprint"));

Also it might be even better to do :

bool print = (argc < 3 || strcmp(argv[2], "noprint"));

---

    if(!primes[l]) {
        //cout << l << " is false" << endl;
        continue;
    }
    for(unsigned long long cl = 2*l; cl < numt; cl+= l) {
        //cout << cl << ", a multiple of " << l << endl;
        primes[cl] = false;
    }

can be written :

    if(primes[l]) {
        for(unsigned long long cl = 2*l; cl < numt; cl+= l) {
            //cout << cl << ", a multiple of " << l << endl;
            primes[cl] = false;
        }
    }

---

In for(unsigned long long l = 0; l<=sqrtt; l++), you can start from index 2. Please note that if you forget to initialise prime[0] to false, you'll get stuck in an infinite loop.

---

In for(unsigned long long cl = 2*l; cl < numt; cl+= l), you can start at index l*l because any i*l with i < l should have been crossed out already.

---

if(!skipprint) for(unsigned long long l = 0; l<numt; l++) if(primes[l]) {
    cout << l << endl;
    count ++;
}
if(skipprint) for(unsigned long long l = 0; l<numt; l++) if(primes[l]) count ++;

could be rewritten in many different ways. Most obvious one is to use an else :

if (skipprint) for(unsigned long long l = 0; l<numt; l++) if(primes[l]) count ++;
else for(unsigned long long l = 0; l<numt; l++) if(primes[l]) {
    cout << l << endl;
    count ++;
}

A probably better option in order not to repeat code is to do :

for(unsigned long long l = 0; l<numt; l++) if(primes[l]) {
    if (!skipprint)
        cout << l << endl;
    count ++;
}

---

Also, you should probably write your algorithm in a function on its own. Other optimisation can be analysed like removing all even numbers from the beginning to use a smaller container.

Answer 2

Any better normal Windows API?

The GetTickCount function returns a DWORD not a double.

According to the documentation it wraps every 50 days, so there's a GetTickCount64 function to avoid this problem.

Its resolution is in the 10..60 msec range, which isn't great for measuring the performance of fast code; there's a QueryPerformanceCounter function used with QueryPerformanceFrequency which you can use for measuring shorter intervals.

---

Also, this looks strange to me ...

vector<bool> primes(numt);

Does vector support an unsigned long long size? Maybe you should be using size_t everywhere instead of unsigned long long.