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

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

Я предпочитаю NumPy из-за скорости.

import numpy as np

# Find all prime numbers using Sieve of Eratosthenes
def get_primes1(n):
    m = int(np.sqrt(n))
    is_prime = np.ones(n, dtype=bool)
    is_prime[:2] = False  # 0 and 1 are not primes

    for i in range(2, m):
        if is_prime[i] == False:
            continue
        is_prime[i*i::i] = False

    return np.nonzero(is_prime)[0]

# Find all prime numbers using brute-force.
def isprime(n):
    ''' Check if integer n is a prime '''
    n = abs(int(n))  # n is a positive integer
    if n < 2:  # 0 and 1 are not primes
        return False
    if n == 2:  # 2 is the only even prime number
        return True
    if not n & 1:  # all other even numbers are not primes
        return False
    # Range starts with 3 and only needs to go up the square root
    # of n for all odd numbers
    for x in range(3, int(n**0.5)+1, 2):
        if n % x == 0:
            return False
    return True

# To apply a function to a numpy array, one have to vectorize the function
def get_primes2(n):
    vectorized_isprime = np.vectorize(isprime)
    a = np.arange(n)
    return a[vectorized_isprime(a)]

Проверьте вывод:

n = 100
print(get_primes1(n))
print(get_primes2(n))    
    [ 2  3  5  7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97]
    [ 2  3  5  7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97]

Сравните скорость сита Эратосфена и грубую силу на ноутбуке Jupyter.Сито Эратосфена в 539 раз быстрее, чем грубой силой на миллион элементов.

%timeit get_primes1(1000000)
%timeit get_primes2(1000000)
4.79 ms ± 90.3 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
2.58 s ± 31.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Answer 2

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

import itertools

def primes():

    class counter:
        def __init__ (this,  n): this.n, this.current,  this.isVirgin = n, n*n,  True
            # isVirgin means it's never been incremented
        def advancePast (this,  n): # return true if the counter advanced
            if this.current > n:
                if this.isVirgin: raise StopIteration # if this is virgin, then so will be all the subsequent counters.  Don't need to iterate further.
                return False
            this.current += this.n # pre: this.current == n; post: this.current > n.
            this.isVirgin = False # when it's gone, it's gone
            return True

    yield 1
    multiples = []
    for n in itertools.count(2):
        isPrime = True
        for p in (m.advancePast(n) for m in multiples):
            if p: isPrime = False
        if isPrime:
            yield n
            multiples.append (counter (n))

Вы заметите, что primes() является генератором, поэтому вы можете сохранить результаты в списке или использовать их напрямую. Вот первые n простых чисел:

import itertools

for k in itertools.islice (primes(),  n):
    print (k)

И, для полноты, вот таймер для измерения производительности:

import time

def timer ():
    t,  k = time.process_time(),  10
    for p in primes():
        if p>k:
            print (time.process_time()-t,  " to ",  p,  "\n")
            k *= 10
            if k>100000: return

На всякий случай, если вам интересно, я также написал primes() как простой итератор (с использованием __iter__ и __next__), и он работал почти с той же скоростью. Удивил меня тоже!

Answer 3

Моя реализация:

import math
n = 100
marked = {}
for i in range(2, int(math.sqrt(n))):
    if not marked.get(i):
        for x in range(i * i, n, i):
            marked[x] = True

for i in range(2, n):
    if not marked.get(i):
        print i

Answer 4

Простой взлом скорости: когда вы определяете переменную «простые числа», установите шаг 2 для автоматического пропуска всех четных чисел и установите начальную точку равной 1.

Затем вы можете дополнительно оптимизироватьдля для i в простых числах используйте для i в простых числах [: round (len (простые числа) ** 0.5)].Это резко повысит производительность.Кроме того, вы можете убрать числа, оканчивающиеся на 5, чтобы еще больше увеличить скорость.