HiveBrain v1.2.0
Get Started
← Back to all entries
patterncppMinor

Prime generator from one to n

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
onefromprimegenerator

Problem

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

using namespace std;

#define printprimes() //for each(bool b in primes) cout " " =3) if(!strcmp(argv[2], "noprint")) skipprint = true;

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

Solution

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 = 2l; cl < numt; cl+= l), you can start at index ll 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.

Code Snippets

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

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

Context

StackExchange Code Review Q#45550, answer score: 7

Revisions (0)

No revisions yet.