Problem 61 Prime Numbers Generation time
Back to Problem Solutions forum
Hi, I was attempting problem 61, and I am unsure how to generate all the prime numbers in one second.
Firstly, I used the trial division method, because I feel that Sieve of Eratosthene requires me to know the value of the 200001th prime number in order to set the limit for the range of integers I am looking in. Does this makes sense to you? Because if I set a big number like 10,000,000 as the upper limit, it will take quite a long time too.
Secondly, given my code below in c++, I still required around 50 seconds to generate all 200,000 prime numbers. However outputting any given prime number after that is fast because it is already stored in a vector. Is there really a way to generate all of them in one second??
#include <iostream>
#include <vector>
long int MAX_LIMIT = 200000;
long int generatePrimes(long int position) {
static std::vector<long int> primes;
primes.reserve(MAX_LIMIT);
primes.push_back(2); // 2 is the first prime number
static long int counter = 1; // one prime number in, counter = 1.
static long int x = 3; // 2 is the first prime number, can start counting from 3.
if (position <= counter) {
return primes[position-1];
}
else {
while (counter < position) {
bool flag = true; // flags prime numbers
for (auto it : primes) {
if (x%it == 0) { // x is divisible by any of the current prime numbers
flag = false;
break;
}
if (it*it > x) {
break;
}
}
if (flag) {
primes.push_back(x);
counter++;
}
x+=2;
}
}
return primes[position-1];
}
int main() {
int maxi;
std::cin >> maxi;
int out[maxi];
for (int x = 0; x < maxi; x++) {
std::cin >> out[x];
}
for (auto it : out) {
std::cout << generatePrimes(it) << " ";
}
}
Hi Friend!
Your code is mostly correct and it works in about 1 second on my machine (e.g. typical 2-3 GHz processor is enough) - so you may be running it on some lightweight computer, or older one, or in some simulation / virtualization mode? I use Gnu compiler.
However it has funny small mistake. Try input
2
5 6
it gives result 11 2, the second value is obviously wrong (should be 11 13).
Sieve of Eratosthene requires me to know the value of the 200001th prime number
That's true, though we have approximate formula - amount of primes less than N is roughly N / ln(N), so it's
easy to figure out that N=3,000,000 should be enough. Though probably it will anyway take too long. It's interesting
to check still. UPD I just wrote Eratosthenes in Go, it works same time (about 1 second on my machine) too.
Alright thanks, I am not sure why it takes 50 seconds too. I am using i7 4790 and codeblocks. Thanks for finding a problem with the code, I have corrected it.
Personally, I've found debugging in Code::Blocks to be sluggish. Is it still as slow if you compile, build, and run the executable?