Моя реализация Решета Эратосфена ошибочна?

Я делаю реализацию решета Эратосфена в Python. Возникающая проблема заключается в том, что появляются не все простые числа (в основном с меньшими номерами).

Вот мой код:

def prevPrimes(n):
    from math import sqrt
    from time import time
    start = time()
    if type(n) != int and type(n) != long:
        raise TypeError("Arg (n) must be of <type 'int'> or <type 'long'>")
    if n <= 2:
        raise ValueError("Arg (n) must be at least 2")
    limit, x, num, primes = sqrt(n), 2, {}, []
    for i in range(1, n+1):
        num[i] = True
    while x < limit:
        for i in num:
            if i%x==0:
                num[i] = False
        x += 1
    for i in num:
        if num[i]:
            primes.append(i)
    end = time()
    primes = sorted(primes)
    print round((end - start), 2), ' seconds'
    return primes

Если я введу >>> prevPrimes(1000), я ожидаю, что результат будет начинаться как: [2, 3, 5, 7, 11, 13, 17] и т. д. Однако вот как это выглядит: [1, 37, 41, 43, 47, #more numbers].

Я знаю, что проблема заключается в том, что он указывает «исходные» простые числа (2, 3, 5, 7, 11, 13, 17 и т. д.) как False из-за того, как моя программа проверяет простые числа. Как я могу этого избежать? Заранее спасибо :)


python function primes sieve
person Rushy Panchal    schedule 21.11.2012    source источник
comment
Кстати, это не сито Эратосфена. Настоящий алгоритм вообще не использует %. Это всего лишь пробное деление.   -  person hammar    schedule 21.11.2012

Ответы (4)


arrow_upward
1
arrow_downward

Так что это не было реальной реализацией SoE, которую я написал некоторое время назад, ниже.

number_primes = 10
prime_list = [True]*number_primes

for i in range (2, number_primes):    #check from 2 upwards
  if prime_list[i]:                   #If not prime, don't need to bother about searching
    j = 2
    while j*i < number_primes:        # Filter out all factors of i (2...n * prime)
      prime_list[j*i] = False
      j+=1
person aw4lly    schedule 21.11.2012

arrow_upward
1
arrow_downward

Иногда, когда вы перебираете num, x равно i, поэтому i % x равно 0, а i помечается как не простое число.

Вам нужно добавить if not x == i: где-нибудь в цикле while, например:

while x < limit:
        for i in num:
            if not x == i:
                if num[i] and i%x==0:
                    num[i] = False
person Marius    schedule 21.11.2012
comment
Кроме того, хотя это вполне может найти простые числа, на самом деле это не метод решета Эратосфена, это скорее метод грубой силы. - person Marius; 21.11.2012

arrow_upward
1
arrow_downward

Во-первых, ответ на ваш конкретный вопрос. Вы отбрасываете простые числа меньше квадратного корня из n. Самое простое решение — изменить строку num[i] = False на num[i] = (not x == i) в конце вашего внутреннего цикла (я думаю, что это работает, я не проверял).

Во-вторых, ваш алгоритм представляет собой пробное деление, а не решето Эратосфена, и будет иметь временную сложность O (n ^ 2) вместо O (n log log n). Оператор по модулю выдает игру. Простейшее Решето Эратосфена выглядит так (псевдокод, который можно перевести на Python):

function primes(n)
  sieve := makeArray(2..n, True)
  for p from 2 to n step 1
    output p
    for i from p+p to n step p
      sieve[i] := False

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

person user448810    schedule 21.11.2012

arrow_upward
0
arrow_downward

время импорта

деф Primes_sieve1():

limitn = int(raw_input("Please enter an upper limit ")) +1
start = time.clock()
primes = {
    }

for i in range(2, limitn):
    primes[i] = True

for i in primes:
    factors = range(i,limitn, i)
    for f in factors[1:]:
        primes[f] = False

end = time.clock()
print "This took ",end-start," seconds"
return [i for i in primes if primes[i]==True]

Primes_sieve1 ()

Вместо использования деления этот код берет кратные всем числам меньше корня предела и изменяет их на false. Это несколько быстрее, поскольку не требует деления каждого числа на какое-то другое число.

Также ниже 1000 возникает ситуация, когда простое число само по модулю дает 0, и поэтому программа считает, что оно ложно. Поскольку sqrt(1000) примерно равен 31, будут затронуты простые числа меньше 31.

Например, на 7-м цикле «пока x ‹ limit» возникает такая ситуация, что: 7%7 == 0, поэтому 7 в вашей программе окажется ложным. Это произойдет для всех простых чисел, меньших предела цикла «пока x ‹ limit», поскольку x в какой-то момент будет простым числом, которое вы пытаетесь найти.

person Aaron    schedule 18.02.2015