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

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

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

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

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

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) вместо его двойного.)

Удаление с начала массива (списка) требует перемещения всех элементов после него вниз. Это означает, что удаление каждого элемента из списка таким образом, начиная с фронта, является операцией 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

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

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))

Я понимаю, что на самом деле это не отвечает на вопрос о том, как быстро генерировать простые числа, но, возможно, некоторые найдут эту альтернативу интересной: поскольку 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 существует, потому что алгоритм работает до тех пор, пока он не взорвет стек, а без блока try отображается обратная трассировка, подталкивая фактический результат, который вы хотите увидеть, за пределами экрана.

Объединив вклад многих энтузиастов (включая Гленна Мейнарда и 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 ms
• 4 : 2.4 ms
• 5 : 23 ms
• 6 : 0.26 s
• 7 : 3.1 s
• 8 : 33 s

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

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

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

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

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

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__), и он работал почти с той же скоростью. Меня тоже удивило!

Я предпочитаю 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 Notebook. Сито Эратосфена в 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)

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

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

Используя немного numpy, я мог найти все простые числа меньше 100 миллионов чуть более чем за 2 секунды.

Следует отметить две ключевые особенности.

• Вырезать кратные i только для i до корня n
• Установка кратных i на False с помощью x[2*i::i] = False намного быстрее, чем явный цикл for в python.

Эти два значительно ускоряют ваш код. Для пределов менее одного миллиона нет заметного времени работы.

import numpy as np

def primes(n):
    x = np.ones((n+1,), dtype=np.bool)
    x[0] = False
    x[1] = False
    for i in range(2, int(n**0.5)+1):
        if x[i]:
            x[2*i::i] = False

    primes = np.where(x == True)[0]
    return primes

print(len(primes(100_000_000)))

Самая быстрая реализация, которую я мог придумать:

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

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

def nondivsby2():
    j = 1
    while True:
        j += 2
        yield j

def nondivsbyk(k, nondivs):
    j = 0
    for i in nondivs:
        while j < i:
            j += k
        if j > i:
            yield i

def primes():
    nd = nondivsby2()
    while True:
        p = next(nd)
        nd = nondivsbyk(p, nd)
        yield p

def main():
    for p in primes():
        print(p)

Я сделал однострочную версию Сита Эратосфена

sieve = lambda j: [print(x) for x in filter(lambda n: 0 not in map(lambda i: n % i, range(2, n)) and (n!=1)&(n!=0), range(j + 1))]

Что касается производительности, я почти уверен, что это не самая быстрая вещь в любом случае, а с точки зрения читаемости / следования PEP8 это довольно ужасно, но это скорее новизна длины, чем что-либо еще.

РЕДАКТИРОВАТЬ: Обратите внимание, что это просто печатает сито и не возвращает (если вы попытаетесь распечатать его, вы получите список Nones, если вы хотите вернуться, измените print (x) в понимании списка только на x.

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

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)))

не уверен, что мой код эффективен, кто-нибудь хочет прокомментировать?

from math import isqrt

def isPrime(n):
    if n >= 2: # cheating the 2, is 2 even prime?
        for i in range(3, int(n / 2 + 1),2): # dont waste time with even numbers
            if n % i == 0:
                return False
    return True

def primesTo(n): 
    x = [2] if n >= 2 else [] # cheat the only even prime
    if n >= 2:
        for i in range(3, n + 1,2): # dont waste time with even numbers
            if isPrime(i):
                x.append(i)  
    return x

def primes2(n): # trying to do this using set methods and the "Sieve of Eratosthenes"
    base = {2} # again cheating the 2
    base.update(set(range(3, n + 1, 2))) # build the base of odd numbers
    for i in range(3, isqrt(n) + 1, 2): # apply the sieve
        base.difference_update(set(range(2 * i, n + 1 , i)))
    return list(base)

print(primesTo(10000)) # 2 different methods for comparison
print(primes2(10000))

Вероятно, самый быстрый способ получить первичные числа - это следующий:

import sympy
list(sympy.primerange(lower, upper+1))

Если вам не нужно их хранить, просто используйте приведенный выше код без преобразования в list. sympy.primerange - это генератор, поэтому он не потребляет память.

Использование рекурсии и оператора моржа:

def prime_factors(n):
    for i in range(2, int(n ** 0.5) + 1):
        if (q_r := divmod(n, i))[1] == 0:
            return [i] + factor_list(q_r[0])
    return [n]