Сито Эратосфена - Поиск простых чисел Питона

Question

Просто чтобы уточнить, это не домашняя задача:)

Я хотел найти простые числа для математического приложения, которое я строю, и наткнулся на Сито Эратосфена подход.

Я написал его реализацию на Python.Но это ужасно медленно.Например, если я хочу найти все простые числа менее 2 миллионов.Это займет> 20 минут.(Я остановил это в этот момент).Как я могу ускорить это?

def primes_sieve(limit):
    limitn = limit+1
    primes = range(2, limitn)

    for i in primes:
        factors = range(i, limitn, i)
        for f in factors[1:]:
            if f in primes:
                primes.remove(f)
    return primes

print primes_sieve(2000)

ОБНОВЛЕНИЕ: Я закончил профилированием этого кода и обнаружил, что довольно много времени было потрачено на удаление элемента из списка.Вполне понятно, учитывая, что он должен пройти весь список (в худшем случае), чтобы найти элемент, а затем удалить его и затем перенастроить список (может быть, какая-то копия продолжается?).Во всяком случае, я вычеркнул список для словаря.Моя новая реализация -

def primes_sieve1(limit):
    limitn = limit+1
    primes = dict()
    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
    return [i for i in primes if primes[i]==True]

print primes_sieve1(2000000)

Answer 1

Вы не совсем реализуете правильный алгоритм:

В вашем первом примере primes_sieve не поддерживает список флагов первичности для удара / сброса (как в алгоритме), но вместо этого изменяет размерынепрерывный список целых чисел, что очень дорого: удаление элемента из списка требует сдвига всех последующих элементов на единицу.

Во втором примере primes_sieve1 поддерживает словарь изФлажки primality - это шаг в правильном направлении, но он перебирает словарь в неопределенном порядке и избыточно выделяет факторы факторов (а не только факторы простых чисел, как в алгоритме).Это можно исправить, отсортировав ключи и пропустив непростые числа (что уже делает его на порядок быстрее), но гораздо эффективнее просто использовать список напрямую.

Правильный алгоритм (ссписок вместо словаря) выглядит примерно так:

def primes_sieve2(limit):
    a = [True] * limit                          # Initialize the primality list
    a[0] = a[1] = False

    for (i, isprime) in enumerate(a):
        if isprime:
            yield i
            for n in range(i*i, limit, i):     # Mark factors non-prime
                a[n] = False

(обратите внимание, что это также включает в себя алгоритмическую оптимизацию запуска непростой маркировки в квадрате простого числа (i*i) вместо его двойного.)

Answer 2

def eratosthenes(n):
    multiples = []
    for i in range(2, n+1):
        if i not in multiples:
            print (i)
            for j in range(i*i, n+1, i):
                multiples.append(j)

eratosthenes(100)

Answer 3

Удаление из начала массива (списка) требует перемещения всех элементов после него вниз. Это означает, что удаление каждого элемента из списка таким образом, начиная с фронта, является операцией O (n ^ 2).

Вы можете сделать это намного эффективнее с помощью наборов:

def primes_sieve(limit):
    limitn = limit+1
    not_prime = set()
    primes = []

    for i in range(2, limitn):
        if i in not_prime:
            continue

        for f in range(i*2, limitn, i):
            not_prime.add(f)

        primes.append(i)

    return primes

print primes_sieve(1000000)

... или, альтернативно, избегайте перестановки списка:

def primes_sieve(limit):
    limitn = limit+1
    not_prime = [False] * limitn
    primes = []

    for i in range(2, limitn):
        if not_prime[i]:
            continue
        for f in xrange(i*2, limitn, i):
            not_prime[f] = True

        primes.append(i)

    return primes

Answer 4

намного быстрее:

import time
def get_primes(n):
  m = n+1
  #numbers = [True for i in range(m)]
  numbers = [True] * m #EDIT: faster
  for i in range(2, int(n**0.5 + 1)):
    if numbers[i]:
      for j in range(i*i, m, i):
        numbers[j] = False
  primes = []
  for i in range(2, m):
    if numbers[i]:
      primes.append(i)
  return primes

start = time.time()
primes = get_primes(10000)
print(time.time() - start)
print(get_primes(100))

Answer 5

Объединив вклады многих энтузиастов (включая Гленна Мейнарда и MrHIDEn из вышеупомянутых комментариев), я придумал следующий фрагмент кода в python 2:

def simpleSieve(sieveSize):
    #creating Sieve.
    sieve = [True] * (sieveSize+1)
    # 0 and 1 are not considered prime.
    sieve[0] = False
    sieve[1] = False
    for i in xrange(2,int(math.sqrt(sieveSize))+1):
        if sieve[i] == False:
            continue
        for pointer in xrange(i**2, sieveSize+1, i):
            sieve[pointer] = False
    # Sieve is left with prime numbers == True
    primes = []
    for i in xrange(sieveSize+1):
        if sieve[i] == True:
            primes.append(i)
    return primes

sieveSize = input()
primes = simpleSieve(sieveSize)

Время, затраченное на вычисления на моей машине для различныхвходы мощностью 10 составляют:

• 3: 0,3 мс
• 4: 2,4 мс
• 5: 23 мс
• 6: 0,26 с
• 7: 3,1 с
• 8: 33 с

Answer 6

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

def intsfrom(n):
    while True:
        yield n
        n += 1

def sieve(ilist):
    p = next(ilist)
    yield p
    for q in sieve(n for n in ilist if n%p != 0):
        yield q


try:
    for p in sieve(intsfrom(2)):
        print p,

    print ''
except RuntimeError as e:
    print e

Блок try существует, потому что алгоритм работает до тех пор, пока он не ударит стек и без Попытайтесь заблокировать отображение обратной трассировки, нажимая фактический вывод, который вы хотите видеть за пределами экрана.

Answer 7

я думаю, что это самый короткий код для поиска простых чисел методом эратосфена

def prime(r):
    n = range(2,r)
    while len(n)>0:
        yield n[0]
        n = [x for x in n if x not in range(n[0],r,n[0])]


print(list(prime(r)))

Answer 8

Моя самая быстрая реализация:

isprime = [True]*N
isprime[0] = isprime[1] = False
for i in range(4, N, 2):
    isprime[i] = False
for i in range(3, N, 2):
    if isprime[i]:
        for j in range(i*i, N, 2*i):
            isprime[j] = False

Answer 9

import math
def sieve(n):
    primes = [True]*n
    primes[0] = False
    primes[1] = False
    for i in range(2,int(math.sqrt(n))+1):
            j = i*i
            while j < n:
                    primes[j] = False
                    j = j+i
    return [x for x in range(n) if primes[x] == True]

Answer 10

Я подумал, что должна быть возможность просто использовать пустой список в качестве завершающего условия для цикла, и придумал это:

limit = 100
ints = list(range(2, limit))   # Will end up empty

while len(ints) > 0:
    prime = ints[0]
    print prime
    ints.remove(prime)
    i = 2
    multiple = prime * i
    while multiple <= limit:
        if multiple in ints:
            ints.remove(multiple)
        i += 1
        multiple = prime * i