Ruby 1.8 prime succ algorithm

Question

I searched every site that I can imagine and cannot determine the basic algorithm that ruby ​​1.8 uses to create a list of primes in the Prime class under mathn. The following is an executable version of the succ method called 100 times (to find the 100th number). Does anyone know how this works?

number_of_primes = 100 seed = 1 primes = Array.new counts = Array.new while primes.size < number_of_primes i = -1 size = primes.size while i < size if i == -1 seed += 1 i += 1 else while seed > counts[i] counts[i] += primes[i] end if seed != counts[i] i += 1 else i = -1 end end end primes.push seed counts.push (seed + seed) end puts seed 

Actual code, of course: http://ruby-doc.org/stdlib-1.8.7/libdoc/mathn/rdoc/Prime.html

It does not look like a sieve algorithm, since there is no predefined list for sifting, it is not a trial division algorithm, since there are no division operations or a module. I am completely at a dead end.

Answer 1

The algorithm is based on a sieve of Eratosthenes.

seed is an integer that is checked for roughness. primes - a list of primes is less than seed and counts contains the corresponding least multiple, which is greater than seed .

Think of counts as a list of “next” crossed out numbers, but only one for each constantly updated one. When finding the next largest multiple, if we get exactly seed , then this is not simple, so it resets the outer loop (using i=-1 ).

Only when we updated the list of large multiple values ​​without meeting exactly the seed , can we conclude that seed is simple.

Here the code is a bit simplified and commented out:

 number_of_primes = 100 seed = 1 primes = [] counts = [] while primes.size < number_of_primes seed += 1 i = 0 while i < primes.size # For each known prime while seed > counts[i] # Update counts to hold the next multiple >= seed counts[i] += primes[i] # by adding the current prime enough times end if seed != counts[i] i += 1 # Go update next prime else i = 0 # seed is a multiple, so start over... seed += 1 # with the next integer end end # The current seed is not a multiple of any of the previously found primes, so... primes.push seed counts.push (seed + seed) end puts seed