patterncppMinor
Prime generator from one to n
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.
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 :
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.
can become :
which is nothing but :
Also it might be even better to do :
can be written :
In
In
could be rewritten in many different ways. Most obvious one is to use an
A probably better option in order not to repeat code is to do :
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.
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.