Efficient Prime Number Generator in c++

Question

I am trying to make an efficient prime number calculator. I've seen ones that can go up to close to 1 trillion in right around 4 hours, however I left mine on overnight and didn't get anywhere near that. I am asking this to see if anyone here knows a more efficient way for me to get up to a really high number really quickly. I also want to see if my everything else is up to standard as this is only my "2nd year" (classes where you self teach) coding.

#include <vector>
#include <iostream>

int main()
{
    std::vector<int> primes;  //vector that will have all numbers in it
    primes.push_back(3);      //push back the first 2 primes (not 2 due to never checking % 2 numbers)
    primes.push_back(5);
    for (unsigned long long i = 7;; i += 2)  //loop controlling the number that will be output
    {
        for (int j = 0; i % primes[j] != 0; ++j)  //loop that "scrolls" through my vector
        {
            if (sqrt(i) <= primes[j])  //if the square root of the number you're outputting is lower than the number you're checking against
            {
                std::cout << i << std::endl;  //output
                primes.push_back(i);  
                break;
            }
            else
                continue;
        }
    }
    return 0;
}

Answer 1

The std::vector<> is a dynamically sized container. The allocation strategy is implementation dependent, but for sake of the argument, assume the .capacity() of a std::vector<> starts off at 1 and doubles each time the vector's size exceeds the current capacity. This capacity increase requires a reallocation of storage, and possibly a copying of the entire array contents to a new location. If you are generating 1 trillion primes, you'll need 40 reallocations and will have done 1 trillion number copies over the course of the 40 reallocations. This is wasting time. If the operating system gets involved with virtual memory paging, you are going to suck up a lot more time.

This overhead can be eliminated by simply .reserve(size_type n)-ing the expected size of the vector ahead of time. With sufficient memory allocated to the vector upfront, no reallocations will occur, and no copies will occur.

---

    for (unsigned long long i = 7;; i += 2) 
    {
        for (int j = 0; i % primes[j] != 0; ++j)  
        {
            if (sqrt(i) <= primes[j]) 
            {

When i is a prime number or semi-prime number in the order of, say, one million, you are looping over all the prime numbers upto the square root of a million, to see if any of them can divide your current number.

How many different values will sqrt(i) evaluate to over those thousand iterations? Or phrased another way, how many times are you computing the same square root? You may want to move that sqrt(i) calculation out of the inner loop.

---

    for (unsigned long long i = 7;; i += 2) 

If you let this loop run over night, or even over a fort-night, will this loop ever end? No! i will overflow the long long and become negative, and slowly increment back towards positive numbers and repeat. Forever is not long enough. Use, at the very least, i > 0 as the loop test condition.

---

A long long has at least 64 bits. A double has only a 52 bit mantissa. This means when you pass a large long long to sqrt( ), you will end up losing a few bits of precision, which can make your sqrt() return slightly the wrong value. When you test sqrt(i) <= primes[j], if i is greater than 2^52, and is a perfect square, you might return a value slightly less than the correct value and fail to test the last prime value, and erroneously declare the perfect square a prime number.

---

You are stuffing long long values into a std:vector<int> container. After a while, they ain't gonna fit.

---

You are using long long for your prime number candidates, which means you expect to find some prime numbers above 2^31.

The Prime Number Theorem tells us the density of prime numbers in that range to be around 1/21. Or, after testing numbers up to 21 billion, you should have found around 1 billion prime numbers.

Your prime number index j is declared as an int. An int is only guaranteed to have 16 bits. You would need at least a long to guarantee 32 bits. But if you hope to find prime numbers up to 2^52, you have to expect to find 2^45 primes, which even exceeds a long. Your j index should be a long long as well.

---

Finally, as mentioned in the comments, look at the Sieve of Eratosthenes.

Answer 2

This might be a peripheral advice

using std::cout is a slow procedure, you may do better with defining a temporary buffer of some significant size and use std::cout as soon as the buffer fills then reuse the buffer.