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?

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.