ruby ​​1.8 prime succ algorithm

Question

나는 상상할 수있는 모든 사이트를 검색했으며, 루비 1.8이 mathn의 Prime 클래스에 소수의리스트를 생성하기 위해 사용하는 기본 알고리즘을 결정할 수 없다. 다음은 100 번 호출 된 succ 메소드의 실행 가능한 버전입니다 (100 번째 소수를 찾으려면). 아무도 이것이 어떻게 작동 하는지를 압니까? http://ruby-doc.org/stdlib-1.8.7/libdoc/mathn/rdoc/Prime.html

가려 할 미리 정의 된 목록이 없기 때문에 그것은 체 알고리즘처럼 보이지 않는이 어떤 부문 없거나으로,이 시험 분할 알고리즘이 아니다 :

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 

실제 코드는 물론이고 모듈러스 연산. 나는 완전히 엉망이다.

Answer 1

알고리즘은 Eratosthenes의 체를 기반으로합니다.

seed은 익명 성을 테스트하는 정수입니다. primes은 seed보다 작은 소수의리스트이고 counts은 seed보다 큰 해당하는 가장 작은 배수를 유지합니다.

counts은 "다음"넘어온 숫자의 목록으로 생각되지만 소수 당 하나만 지속적으로 업데이트됩니다. 그 다음으로 큰 배수를 찾을 때 정확하게 seed이되면 소수가 아니므로 바깥 쪽 루프를 다시 설정합니다 (i=-1). 우리가 정확히 seed가 발생하지 않고, 더 큰 배수의 목록을 업데이트 한 만

, 우리는 seed 총리는 것을 추론 할 수있다.

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