Pagini: [1]   În jos
 Ajutor Subiect: Problem: Prime Number Generator  (Citit de 6641 ori) 0 Utilizatori şi 1 Vizitator pe acest subiect.
Cosmin
Echipa infoarena
Nu mai tace

Karma: 351
Deconectat

Mesaje: 1.799

 « : Ianuarie 25, 2016, 08:43:10 »

http://www.infoarena.ro/blog/primegenerator
 Memorat
dutzul
De-al casei

Karma: 42
Deconectat

Mesaje: 119

 « Răspunde #1 : Ianuarie 25, 2016, 09:08:09 »

is extra memory allowed?
 Memorat
Cosmin
Echipa infoarena
Nu mai tace

Karma: 351
Deconectat

Mesaje: 1.799

 « Răspunde #2 : Ianuarie 25, 2016, 09:10:51 »

Yes
 Memorat
sciobaca
Strain

Karma: 5
Deconectat

Mesaje: 24

 « Răspunde #3 : Ianuarie 25, 2016, 10:20:45 »

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

`PrimeGenerator:   primes = []   next = 2PrimeGenerator.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()`
 Memorat
Cosmin
Echipa infoarena
Nu mai tace

Karma: 351
Deconectat

Mesaje: 1.799

 « Răspunde #4 : Ianuarie 25, 2016, 10:42:02 »

Is it amortized?
 Memorat
Cosmin
Echipa infoarena
Nu mai tace

Karma: 351
Deconectat

Mesaje: 1.799

 « Răspunde #5 : Ianuarie 25, 2016, 10:54:30 »

Neat, I was thinking about amortized . But I guess one can do it as fast and not amortized .
 Memorat
dutzul
De-al casei

Karma: 42
Deconectat

Mesaje: 119

 « Răspunde #6 : Ianuarie 25, 2016, 11:09:43 »

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

 Memorat
Cosmin
Echipa infoarena
Nu mai tace

Karma: 351
Deconectat

Mesaje: 1.799

 « Răspunde #7 : Ianuarie 25, 2016, 11:25:19 »

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.
 Memorat
freak93
Echipa infoarena
Nu mai tace

Karma: 341
Deconectat

Mesaje: 804

 « Răspunde #8 : Ianuarie 26, 2016, 01:44:54 »

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).
 « Ultima modificare: Ianuarie 26, 2016, 03:04:42 de către Budau Adrian » Memorat
freak93
Echipa infoarena
Nu mai tace

Karma: 341
Deconectat

Mesaje: 804

 « Răspunde #9 : Ianuarie 26, 2016, 11:29:32 »

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.
 Memorat
mathboy
Moderatori infoarena
Nu mai tace

Karma: 150
Deconectat

Mesaje: 259

 « Răspunde #10 : Ianuarie 28, 2016, 22:40:46 »

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!
 « Ultima modificare: Ianuarie 28, 2016, 22:47:17 de către Dragos-Alin Rotaru » Memorat
freak93
Echipa infoarena
Nu mai tace

Karma: 341
Deconectat

Mesaje: 804

 « Răspunde #11 : Ianuarie 31, 2016, 01:14:29 »

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.
 Memorat
 Pagini: [1]   În sus
Schimbă forumul: