Problem: Prime Number Generator

[•Cosmin]

http://www.infoarena.ro/blog/primegenerator

[•dutzul]

is extra memory allowed?

[•Cosmin]

Yes

[•sciobaca]

You can adapt most of the usual algorithms for checking primality. For example:

PrimeGenerator:
   primes = []
   next = 2

PrimeGenerator.nextPrime:
   isprime = true
   for i in primes:
      if next % i != 0:
        isprime = false
        break
   if isprime:
      primes.add(next)
      next++
      return next
   else:
      next++
      return nextPrime()

[•Cosmin]

Is it amortized?

[•Cosmin]

Neat, I was thinking about amortized . But I guess one can do it as fast and not amortized .

[•dutzul]

My idea is a combination between the way STL <vector> is built  and the  Erathostene sieve ideea

Lets consider the all numbers in the interval 1..2^32
Lets create 32 bins in the following manner:
The bin with index i holds the values  1..2^i   .( example: bin number 16 holds the values 1,2,3...2^16)


Lets  define the folowing method :

vector<int> Erathostenes (Max_Value)
{
   ..../// here it finds all the primes in the interval 1..Max_Value using the Erathostenes sieve
   .../// it returns a <vector> int with all the primes in the interval 1..Max_Value
}

as we get a new query , we might "move" into a new bin (ie: a bin with a bigger index) (indexes range from 1 to 32)
each time we move in a new bin we refresh our prime list callling the above method

The amortized running time is NlogN.
The worst case is also NlogN , because when we first get into a new bin we do NlogN operations
but all the other numbers that don't belong to the begining of a bin are accesed in constant time

[•Cosmin]

Dan, I was thinking of the same idea. Use eratosthenes sieve and each time I run out of prime numbers, double the array and run the sieve again.

Tomek has a solution that is not amortized which does log n log log n work for each number.

[•freak93]

I believe I have O(log p) worst case for each operation where p is the current prime. I'm gonna follow up with an implementation.

Later Edit: Here is the source code: http://ideone.com/NnOU63, fairly simple to understand why nextPrime takes logP, probably hard to understand why it is correct.

Tested on my pc for primes under 4 * 10^8, and it is correct (although it takes some time because of the very high constant behind the complexity). After that allocations start failing (or i might end up overflowing, but its already a big enough number for confirmation).

[•freak93]

Yep, my bad. Somehow I thought vector<int> for basic types does not 0-initialize. unique_ptr<int[...]> should solve it depending on the malloc implementation, which can be O(log size) if manually-written.

[•mathboy]

@Adrian: Could you please explain your idea in one paragraph (or maybe 2)?

I think it's worth an explanation and people (including me) usually prefer natural language instead of C++ code - also because I'm lazy.

Thanks!

[•freak93]

It's kind of like a real-time hash:

Check https://en.wikipedia.org/wiki/Hash_table for "Incremental Resizing".

What I do is just simulate the linear time sieve of Erathostenes.

Normally for amortized cost, you would just double(or any k * size with k > 1.5) the size of the array.
For incremental resizing, you allocate the memory for the bigger array before you fill the smaller one (allocation is supposed to be fast, at least in single threaded programs). Then at each step you would answer from the already solved sieve (the smaller one) but do some extra computation in the bigger one such as by the time you finish with the smaller sieve, the big one is up and ready.

I've added comments in the source code which should also help with understanding.