Почему этот наивный алгоритм простого числа не работает?

Question

Я пытаюсь реализовать this "find the nth prime number" algorithm в Ruby 2.1.

Я также отметил его «алгоритм», потому что я думаю, что вопрос является агностиком языка, а написанный на Ruby код достаточно прост для чтения, даже если вы незнакомы. Я использовал имена описательных переменных, чтобы помочь им.

1. Итерация над системой целого числа, не обращая внимания даже число больше, чем 2 (2, 3, 5, 7, ...)
2. Для каждого целого р, проверить, если р первична:
   1. Итерация над найденными штрихами, которые меньше квадратного корня p
   2. Для каждого штриха в этом наборе f проверяем, является ли он фактором p: i. Если f делит p, то p не является простым. Продолжите с 2 для следующего p.
   3. Если факторов не найдено, p является простым. Продолжить до 3.
3. Если p не является n-го числа, мы нашли его, добавив его в список простых чисел. Продолжите с 2 для следующего p.
4. В противном случае p является n-го числа, которое мы нашли, и мы должны его вернуть.

Звучит достаточно просто. Итак, я пишу мой метод (функция):

def nth_prime(n) 
     primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] 

     primes[-1].upto(Float::INFINITY) do |p| 
      return primes[n-1] if primes.length >= n-1 
      possible_prime = true 
      primes_to_check = primes.select{|x|x<=Math.sqrt(p)} 
      primes_to_check.each do |f| 
       if f%p==0 
        possible_prime = false 
        break 
       end 
      end 
      primes << p if possible_prime 
     end 
    end 

Цель состоит в том, чтобы сказать nth_prime(10) и получить 10-простое число.

Чтобы объяснить свою логику:

я начинаю со списком известных простых чисел, так как алгоритм требует. Я перечислю первую десятку.

Затем я перебираю всю систему чисел. (primes[-1]+2).upto(Float::Infinity) do |p| предложит каждое число от последнего известного простого плюс два (так как +1 приведет к четному числу, а равно 2 не может быть простым) до бесконечности к отступом, как p. Я не пропустил даже номера и имеют

Первое, что я делаю, это вернуть п е простое число, если список известных простых чисел уже давно, по крайней мере п элементов. Это работает для известных значений - если вы попросите 5-го, вы получите 11 в результате.

Затем я установил флаг, possible_prime, на true. Это означает, что ничего не найдено, не премьер еще. Я собираюсь сделать некоторые тесты, и если он выживет без изменения флага на false, то p окажется простым и добавляется к массиву известных простых чисел. В конце концов этот массив будет равен n и вернет n-е значение.

Я создаю массив, primes_to_check, содержащий все известные простые числа < = квадратный корень из p. Каждый из них проверяется по очереди как f.

Если е можно аккуратно разделить р, я знаю, что р не является простым, так что я изменить флаг false и break, что приводит нас из петли штрихов-к-чека и обратно в upto- бесконечность. В этом цикле осталось только одно утверждение, которое добавляется к массиву известных простых чисел, если флаг является истинным, а это не так, мы перезапускаем цикл со следующим числом.

Если нет f s не может чисто разделить р то р должен быть простым, а значит, сохраняется до конца цикла штрихов-к-проверки с флагом до сих пор установить истинно, и достигает конечный «присоединять р к утверждению известных простых чисел.

В конечном итоге это сделает массив primes достаточно длинным, чтобы ответить на вопрос «Что такое n-е правое?».

Проблема

Просить 10 штрих делает принеси мне 29, последний премьер-я поставляемый. Но просить 11 получает nil, или нет значения. Я перечислил код сто раз и не могу представить случай, когда значение не возвращается.

Что я сделал не так?

Answer 1

return primes[n-1] if primes.length >= n-1 

Для primes, чтобы иметь элемент с индексом n-1, он должен иметь длину, по меньшей мере, n.

if f%p==0 

Это проверяет, является ли известный премьер делится на кандидате, не является ли делится известным штрихом кандидата.

primes[-1].upto(Float::INFINITY) do |p| 

Это начинает цикл в расчете уже в списке (29). 29 правильно установлено, что оно является простым, поэтому оно снова добавляется в список. Вы должны начать цикл с числа после 29.

Answer 2

Algorithm for testing prime no.s: 
1)Input num 
2)counter= n-1 
3)repeat 
4)remainder = num%counter 
5)if rem=0 then 
6)broadcast not a prime.no and stop 
7)change counter by -1 
8)until counter = 1 
9)say its a prime and stop