Prime Number Generator

Question

The purpose of this program is to run an infinite prime generator that won't stop unless I tell the console to stop. This is not a sieve of Eratosthenes; it stores prime numbers in an array and divides by those primes to check if they are prime. This allows me to avoid dividing by the multiple of all primes.

Are there any ways I could optimize this program? When I tried to look on the Internet it only gave me sieves, but that wouldn't work for me because those programs need to know a limit.

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int main()
{
int l=0;
bool isprime;
vector<int>primes;
primes.push_back(2);
for (int nur = 3;nur!=0;nur+=2)
{
 isprime = true;
 for (int primecount=0 ;primes[primecount]<=sqrt(nur);primecount++)
 {
 if (nur % primes[primecount] == 0)
 {
 isprime = false;
 break;
 }
 else if (primes[primecount]*primes[primecount]>nur)
 {
 cout<<nur<<endl;
 break;
 }
 }
 if (isprime)
 {
 cout << nur << endl;
 primes.push_back(nur);
 // l++;
 }
}
cout<<"Finished"<<endl;
// cout<<primes[l];
return 0;
}

Answer 1

primes.push_back(2);
for (int nur = 3;nur!=0;nur+=2)
{

A reasonably simple optimization is to get rid of numbers divisible by 3.

int interval = 4;
primes.push_back(2);
primes.push_back(3);
for (int nur = 5; nur != 0; nur += interval)
{
 interval = 6 - interval;

The interval variable will vary between 2 and 4. This will test 5, 7, (skip 9), 11, 13, (skip 15), 17, 19, ... The skipped values are all divisible by three.

It's also not clear when this will stop. Hope that the program will crash on overflow?

• Neeraj Mula: Your right, thank you mdfst13. Could you give me any tips for indenting my code?

Answer 2

First, you could indent your code. Read some of the other C++ code on this site, and look at how the best answers style their code; then copy that style.

While you're reading other code on this site, you could also read other people's prime-sieve implementations and see what they do differently from yours; that is, your question is basically a duplicate of all the questions you see in the "Related" sidebar over there --->.

However, here's one obvious piece of advice for your code specifically:

else if (primes[primecount]*primes[primecount]>nur)

This is redundant with your primes[primecount]<=sqrt(nur) loop condition (modulo off-by-one errors). You should avoid doing any unnecessary math at all in your tightest loop, which means

• getting rid of this multiplication,
• moving the sqrt computation outside the loop (storing int last_candidate = sqrt(n)+1;) and replacing the comparison to double with a plain old int comparison,
• moving the iostreams operations outside of the tight loop (e.g. do a second loop afterward to cout the whole vector at once).

Also notice that in

for (int nur = 3;nur!=0;nur+=2)

a good compiler will optimize away the nur!=0 condition (since obviously you can't get zero by adding a positive number to 3); but if you have a bad compiler, it might actually be generating that extra test every time, so replacing that condition with true would help in that case.

• Sumurai8: Considering nur is odd, even after wrapping around from MAX_INT to the negatives, it shouldn't become 0.
• Quuxplusone: Signed integers in C++ don't actually "wrap around"; they just invoke undefined behavior on overflow. Most compilers these days know this. You can check by replacing nur!=0 with nur!=1 and seeing whether that results in any change to the generated machine code. (On most compilers it won't.)
• Neeraj Mula: What do you mean by last candidate and why would you add 1 to it.
• Christopher Oicles: He wants you to compute sqrt(nur) before the loop, so the slow sqrt function won't be called needlessly for every primecount (but it is likely your compiler recognizes this as a constant value and already hoists the sqrt calculation out of the loop). He suggests adding one in order to match the condition check from the redundant squaring: primes[primecount]*primes[primecount] > nur, but doing this will just give you an extra useless iteration when nur is the square of a prime number, so I would just remove the square check without adding 1 to the candidate value.