Skip to main content
Source Link
Spag
  • 41
  • 2

Efficient Prime Number Generator in c++

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;
}