Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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;
}
share|improve this question

2 Answers 2

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.

share|improve this answer
    
the printprimes was debug which was commented out so I didn't have to remove all the instances. They have all been removed now. The double ifs are there because for some reason the program evaluates both before deciding. primes[0] is always init to false because it represents 0 which is not a prime number. i will always be greater than l. I will take everything you told me in to account, though. –  nimsson Mar 28 at 13:03
    
is sometime frowned upon! Any body doing this in real production code should be shot. FIne if you do it in a ten line program that you write to test something. But anything that goes public should not have it in. Your just shooting the maintainer in the foot. –  Loki Astari Mar 28 at 14:46
    
Yeah @LokiAstari I am not planning on writing an big program for a while yet. If I do, It will be in Java. –  nimsson Mar 28 at 21:47

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.

share|improve this answer
    
vector does support unsigned long long. at least on visual studio. –  nimsson Mar 28 at 13:06
    
ULONGLONG means 64-bit on a Windows 32-bit machine. When you say that "vector does support unsigned long long" is that on 32-bit or 64-bit windows? Have you tried it with a number bigger than 2<sup>32</sup>? Don't you agree that size_t (or vector::size_type) is the only type that vector really supports as a constructor parameter? –  ChrisW Mar 28 at 15:33
    
64 bit windows... 2^32 is larger than the amount of ram than my system has. I have exactly 4GB of memory. –  nimsson Mar 28 at 19:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.