HiveBrain v1.2.0
Get Started
← Back to all entries
patterncppMinor

Yet Another, Another Prime Generator

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
codereviewprimescppstackoverflowc++performance
yetprimeanothergenerator

Problem

Yes, I realize there are many, many, many, many, many, prime generators on the Code Review SE. However, I have been unable to find any using this method for generating primes inside a vector, so I figure it should be covered.

Here's the C++ code:

long int primeCap = 1e10;
std::vector primes;
primes.push_back(2);
for(long int i = 2; i < primeCap; i++){
    bool isPrime = true;
    for(long int j = 0; primes[j] <= sqrt(i); j++){
        if(i % primes[j] == 0){
            isPrime = false;
            break;
        }
    }
    if(isPrime)
        primes.push_back(i);
}


This code takes a while to fill a vector with \$10^{10}\$ (or more, depending on how much is needed) primes. How can this code be improved for the generation primes?

Update: The issue described below was a nonissue, and was simply an error on my part, the part below can be ignored.

There may also be an issue where the very last item in the vector is set to \$2\$. I have not effectively verified this, but modifying the if(isPrime) statement to be:

if(isPrime){
    std::cout << i << '\n';
    primes.push_back(i);
}


Results in the last output being two. Once again, I have not effectively verified this, but it is something to note.

Solution

Here are some things that may help you improve your code.

Use the required #includes

The code uses std::vector which means that it should #include . It was not difficult to infer, but it helps reviewers if the code is complete.

Use ` instead of

I infer that you've used instead of because you're invoking sqrt(i) rather than std::sqrt(i). The difference between the two include forms is that the former defines things within the std:: namespace versus into the global namespace. Language lawyers have lots of fun with this, but for daily use I'd recommend using . See this SO question for details.

Use the appropriate constructor

There's not really any reason to push the value of 2 after the stack is created when it could be done all at the same time. In fact, I'd write this:

std::vector primes{2, 3};


Seeding the vector with the first two primes for reasons that will be very clear in the next suggestion.

Use a more efficient algorithm

Of all even numbers, only 2, which is already in the vector, is prime, so thereafter all even numbers may be safely skipped. Further, there's little reason to attempt to divide by 2 if you've skipped all other even numbers. For that reason, I'd write it like this:

for(int i = 3; i < primeCap; i+=2) {
    bool isPrime = true;
    int lim = std::sqrt(i);
    for(int j = 1; primes[j] <= lim; j++){
        if(i % primes[j] == 0){
            isPrime = false;
            break;
        }
    }
    if(isPrime)
        primes.push_back(i);
}


Doing this reduces the time by about half.

Use const where practical

Since primeCap doesn't seem to change within this program, it would make sense to me to declare it as const or even constexpr:

constexpr long int primeCap = 1e8;


Maximize the available numerical range

Assuming we're not hunting for negative prime numbers, wouldn't unsigned numbers make more sense? It's also logical to try to assure that primeCap and the values in the std::vector are of the same type -- either unsigned or unsigned long.

Avoid memory reallocations

It would save some reallocations and moves if the code were to preallocate the required size. One quick and relatively accurate approximation for the number of prime numbers less than a particular number \$n\$ is \$\frac{n}{\log{n}-1}\$. We can use that to reserve approximately the right amount of memory:

primes.reserve(primeCap / (std::log(primeCap) - 1));


Avoid breaking out of loops

It's generally better to put loop exit conditions at the top rather than forcing the reader to hunt for a break buried somewhere inside the loop. It also often simplifies the code. The for loop could be rewritten as:

for(unsigned j = 1; isPrime && operator[](j) <= lim; j++){
    isPrime = i % operator[](j);
}


Consider a custom class

If we need a std::vector` of prime numbers, there's little use in it until it's actually created and populated. For that reason, one way to make sure that it's useful immediately after construction is to create a class with a constructor:

Result

Here's the code with all of these suggestions. It runs about twice as fast as the original for any given range.

#include 
#include 
#include 

class Primes : public std::vector
{
public:
    Primes(unsigned primeCap) 
        : std::vector{2,3}
     {
        reserve(primeCap / (std::log(primeCap) - 1));
        for(unsigned i = back()+2; i < primeCap; i+=2) {
            bool isPrime = true;
            unsigned lim = std::sqrt(i);
            for(unsigned j = 1; isPrime && operator[](j) <= lim; j++){
                isPrime = i % operator[](j);
            }
            if(isPrime)
                push_back(i);
        }
    }
};

int main() {
    Primes primes(1e8);
    std::cout << "prime[" << primes.size() << "] = " << primes.back() << "\n";
}

Code Snippets

std::vector<int> primes{2, 3};
for(int i = 3; i < primeCap; i+=2) {
    bool isPrime = true;
    int lim = std::sqrt(i);
    for(int j = 1; primes[j] <= lim; j++){
        if(i % primes[j] == 0){
            isPrime = false;
            break;
        }
    }
    if(isPrime)
        primes.push_back(i);
}
constexpr long int primeCap = 1e8;
primes.reserve(primeCap / (std::log(primeCap) - 1));
for(unsigned j = 1; isPrime && operator[](j) <= lim; j++){
    isPrime = i % operator[](j);
}

Context

StackExchange Code Review Q#145783, answer score: 6

Revisions (0)

No revisions yet.