I rewrote it without the need of the addends list, thus fixing a bug at the same time as improving memory efficiency.
Code:
void extend_primes(I n)
{
static unsigned int primorial_index = 0;
static I primorial = 2;
I base = primes.back() - primes.back() % primorial;
if(primes.back() != base + 1 && prime(base + 1))
primes.push_back(base + 1);
for(auto i = primorial_index + 1;primes.at(i) < primorial && primes.back() < n;i++)
if(prime(base + primes.at(i)))
primes.push_back(base + primes.at(i));
base += primorial;
while(primes.back() < n)
{
if(prime(base + 1))
primes.push_back(base + 1);
for(auto i = primorial_index + 1;primes.at(i) < primorial && primes.back() < n;i++)
if(prime(base + primes.at(i)))
primes.push_back(base + primes.at(i));
base += primorial;
if(primes.back() > primorial * primes.at(primorial_index + 1))
{
primorial_index++;
primorial *= primes.at(primorial_index);
base = primes.back() - primes.back() % primorial;
if(primes.back() < base + 1 && prime(base + 1))
primes.push_back(base + 1);
for(auto i = primorial_index + 1;primes.at(i) < primorial && primes.back() < n;i++)
if(primes.back() < base + primes.at(i) && prime(base + primes.at(i)))
primes.push_back(base + primes.at(i));
base += primorial;
}
}
}
This function generates a list of all primes less than 1000000 and the next prime in about 3.25s consistently, whereas the naive version takes approximately 14.5s consistently:
Code:
void simple_extend_primes(I n)
{
for(auto i = primes.back() + 2;primes.back() < n;i += 2)
if(prime(i))
primes.push_back(i);
}
Notice that both assume that "primes" already contains 2 and 3, at least.
antred: I'm going to add a lock. I was just getting it working before worrying about making it MT.