# Prime generator from one to n

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

-

## 2 Answers

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.

-
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 '14 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 '14 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 '14 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.

-
vector does support unsigned long long. at least on visual studio. – nimsson Mar 28 '14 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 '14 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 '14 at 19:35