Алгоритм - Что не так с этим решением решета Эрастотена

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

Вот мой алгоритм в Ruby для определения, является ли число простым.

def prime?(n)
  primes = [2,3,5,7,9,11,13,17]
  primes.include?(n) || primes.none? { |p| n % p == 0 }
end

Алгоритм работает следующим образом: вы берете первую пару простых чисел, я взял первые 8, чтобы быть в безопасности. Затем я бы отсеял все кратные этим простым числам, поскольку они никак не могут быть простыми.

Следовательно, все остальные числа должны быть простыми

Я был потрясен, узнав, что мои тесты провалились, и я пропустил некоторые цифры. Как это возможно? Я четко следую алгоритму.


ruby algorithm primes sieve-of-eratosthenes
person Richard Hamilton    schedule 30.12.2015    source источник
comment
Любое произведение простых чисел, не входящее в ваш конечный список, будет неправильно классифицировано вашей функцией как простое. Например, 19*19, или 19*23, или 19*29*37.   -  person Paul Hankin    schedule 30.12.2015
comment
Вы вообще не следуете подходу Seive of Erastothenes.   -  person    schedule 30.12.2015
comment
Ответ заключается в том, что вы не следуете алгоритму идеально. И что просто неверно, что после того, как вы отсеете все числа, кратные первым 8 простым числам, все остальные числа станут простыми. en.wikipedia.org/wiki/   -  person jrochkind    schedule 30.12.2015
comment
@ user5301625 : Seive of Erastothenes - это вы издеваетесь над именем с ошибкой или над проверкой орфографии в праздничной коме?   -  person greybeard    schedule 30.12.2015
comment
Нас троллят?   -  person Niklas B.    schedule 30.12.2015

Ответы (3)


arrow_upward
2
arrow_downward

Чтобы проверить простоту заданного числа n, вам нужно проверить, делится ли оно на какое-либо из простых чисел ‹= sqrt(n). Поскольку вы запрограммировали в него простые числа до 17, ваш алгоритм будет работать только для значений n ‹= 172.

Кроме того, вы включили 9 в свой список «простых». Это не должно повлиять на ваш тест, за исключением самого значения 9, поскольку все, что делится на 9, также делится на 3, но это довольно непослушно.

person pjs    schedule 30.12.2015
comment
@CoderX Я не опубликовал ни одного метода, я объяснил ограничения его метода. Какая часть объяснения вам не понятна? - person pjs; 30.12.2015
comment
Подход Seive of Erastothenes не ограничивается ‹= 17*17. Он просто найдет следующее наименьшее незачеркнутое число и удалит все числа, кратные этому числу меньше n. - person ; 30.12.2015
comment
@CoderX Его реализация ограничена 17 * 17. Самые большие числа, которые он может проверить на простоту, ограничены квадратом наибольшего простого числа, которое он включает в свой известный набор. - person pjs; 30.12.2015
comment
да. Но он утверждает, что использует подход Seive of Erastothenes. Но это не так. Значит, ему нужно изменить подход. - person ; 30.12.2015
comment
@CoderX Если у вас есть сомнения по поводу того, чтобы назвать это решетом Эратосфена, ваша жалоба не ко мне. В любом случае алгоритм OP даст правильные ответы о простоте аргумента n для ограниченного диапазона n (после удаления 9). Его вопрос заключался в том, почему его алгоритм иногда давал неправильные ответы, я объяснил почему. - person pjs; 30.12.2015

arrow_upward
2
arrow_downward

Прежде всего, вы включили 9 в список простых чисел. 9 не простое число. Попробуйте следующий подход.

  • Чтобы найти все простые числа до заданного числа. Начните с наименьшего простого числа, 2.
  • Отметьте 2 как простое число и вычеркните все числа, кратные 2.
  • Далее смотрите, какое наименьшее число не зачеркнуто. Оно равно 3. Выведите 3 как простое число и вычеркните все числа, кратные 3, меньшие n.

  • Затем снова выберите следующее наименьшее число, не зачеркнутое, и так далее.

    def primeSeive(n)
    while primes[index]**2 <= primes.last
        prime = primes[index]
        primes = primes.select { |x| x == prime || x%prime != 0 }
        index += 1
end
person Abhishek Kumar    schedule 30.12.2015

arrow_upward
1
arrow_downward

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

В алгоритме решета сначала нужно только 2 в качестве простого числа.

Псевдокод:

Sieve(n) {
  a[1] := 0                          
  for i := 2 to n do a[i] := 1
  p := 2
  while p2  <  n do {
    j := p2
    while (j  <  n) do {             
      a[j] := 0
      j := j+p
    }
    repeat p := p+1 until a[p] = 1   
  }
  return(a)
}

здесь A — массив, значение индекса которого указывает на простоту. 0 для не основного, 1 для основного. в цикле while пометить простые числа кратными и последним выбрать следующее простое число в разделе repeat.

person Abu Hanifa    schedule 30.12.2015