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

Question

Это лучший алгоритм, который я мог придумать.

def get_primes(n):
    numbers = set(range(n, 1, -1))
    primes = []
    while numbers:
        p = numbers.pop()
        primes.append(p)
        numbers.difference_update(set(range(p*2, n+1, p)))
    return primes

>>> timeit.Timer(stmt='get_primes.get_primes(1000000)', setup='import   get_primes').timeit(1)
1.1499958793645562

Можно ли сделать это еще быстрее?

Этот код имеет недостаток: поскольку numbers является неупорядоченным набором, нет гарантии, что numbers.pop() удалит самый низкий номер из набора. Тем не менее, это работает (по крайней мере для меня) для некоторых входных чисел:

>>> sum(get_primes(2000000))
142913828922L
#That's the correct sum of all numbers below 2 million
>>> 529 in get_primes(1000)
False
>>> 529 in get_primes(530)
True

Answer 1

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

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

Конечно, это работает, только если вы знаете верхнюю границу N во время компиляции, но, таким образом, это относится к (почти) всем проблемам Эйлера проекта.

PS: Возможно, я ошибаюсь, хотя разбор исходного кода с помощью жестко запрограммированных простых чисел выполняется медленнее, чем вычисление их в первую очередь, но насколько я знаю, Python запускается из скомпилированного .pyc файлы, поэтому чтение двоичного массива со всеми простыми числами до N должно быть чертовски быстрым в этом случае.

Answer 2

Вот интересный метод генерации простых чисел (но не самый эффективный) с использованием понимания списка Python:

noprimes = [j for i in range(2, 8) for j in range(i*2, 50, i)]
primes = [x for x in range(2, 50) if x not in noprimes]

Пример и некоторые пояснения можно найти прямо здесь

Answer 3

Самый быстрый метод, который я пробовал до сих пор, основан на Python cookbook erat2 функция:

import itertools as it
def erat2a( ):
    D = {  }
    yield 2
    for q in it.islice(it.count(3), 0, None, 2):
        p = D.pop(q, None)
        if p is None:
            D[q*q] = q
            yield q
        else:
            x = q + 2*p
            while x in D:
                x += 2*p
            D[x] = p

См. этот ответ для объяснения ускорения.

Answer 4

Извините, что беспокою, но erat2 () имеет серьезный недостаток в алгоритме.

При поиске следующей композиции нам нужно проверить только нечетные числа. q, p оба нечетны; тогда q + p четно и не нуждается в проверке, но q + 2 * p всегда нечетно. Это исключает проверку «если даже» в цикле while и экономит около 30% времени выполнения.

Пока мы находимся: вместо элегантного метода «D.pop (q, None)» get и delete используют «if в D: p = D [q], del D [q]», в два раза быстрее! По крайней мере, на моей машине (P3-1Ghz). Поэтому я предлагаю эту реализацию этого умного алгоритма:

def erat3( ):
    from itertools import islice, count

    # q is the running integer that's checked for primeness.
    # yield 2 and no other even number thereafter
    yield 2
    D = {}
    # no need to mark D[4] as we will test odd numbers only
    for q in islice(count(3),0,None,2):
        if q in D:                  #  is composite
            p = D[q]
            del D[q]
            # q is composite. p=D[q] is the first prime that
            # divides it. Since we've reached q, we no longer
            # need it in the map, but we'll mark the next
            # multiple of its witnesses to prepare for larger
            # numbers.
            x = q + p+p        # next odd(!) multiple
            while x in D:      # skip composites
                x += p+p
            D[x] = p
        else:                  # is prime
            # q is a new prime.
            # Yield it and mark its first multiple that isn't
            # already marked in previous iterations.
            D[q*q] = q
            yield q

Answer 5

Вот небольшая версия Sieve of Eratosthenes, имеющая как хорошую сложность (ниже, чем сортировка массива длины n), так и векторизацию. По сравнению с @unutbu раз это так же быстро, как пакеты с 46 микросекундами, чтобы найти все простые числа меньше миллиона.

import numpy as np 
def generate_primes(n):
    is_prime = np.ones(n+1,dtype=bool)
    is_prime[0:2] = False
    for i in range(int(n**0.5)+1):
        if is_prime[i]:
            is_prime[i*2::i]=False
    return np.where(is_prime)[0]

Сроки:

import time    
for i in range(2,10):
    timer =time.time()
    generate_primes(10**i)
    print('n = 10^',i,' time =', round(time.time()-timer,6))

>> n = 10^ 2  time = 5.6e-05
>> n = 10^ 3  time = 6.4e-05
>> n = 10^ 4  time = 0.000114
>> n = 10^ 5  time = 0.000593
>> n = 10^ 6  time = 0.00467
>> n = 10^ 7  time = 0.177758
>> n = 10^ 8  time = 1.701312
>> n = 10^ 9  time = 19.322478

Answer 6

Это элегантное и более простое решение для поиска простых чисел с использованием сохраненного списка. Начинается с 4 переменных, вам нужно только проверить нечетные простые числа для делителей, и вам нужно проверить только половину того числа, которое вы проверяете как простое число (нет смысла проверять, делится ли 9, 11, 13 на 17) , Он проверяет ранее сохраненные простые числа как делители.

    # Program to calculate Primes
 primes = [1,3,5,7]
for n in range(9,100000,2):
    for x in range(1,(len(primes)/2)):
        if n % primes[x] == 0:
            break
    else:
        primes.append(n)
print primes

Answer 7

Со временем я собрал несколько сит с простыми числами. Самый быстрый на моем компьютере это:

from time import time
# 175 ms for all the primes up to the value 10**6
def primes_sieve(limit):
    a = [True] * limit
    a[0] = a[1] = False
    #a[2] = True
    for n in xrange(4, limit, 2):
        a[n] = False
    root_limit = int(limit**.5)+1
    for i in xrange(3,root_limit):
        if a[i]:
            for n in xrange(i*i, limit, 2*i):
                a[n] = False
    return a

LIMIT = 10**6
s=time()
primes = primes_sieve(LIMIT)
print time()-s

Answer 8

Это способ, которым вы можете сравнить с другими.

# You have to list primes upto n
nums = xrange(2, n)
for i in range(2, 10):
    nums = filter(lambda s: s==i or s%i, nums)
print nums

Так просто ...

Answer 9

Я медленно отвечаю на этот вопрос, но это казалось забавным упражнением. Я использую NumPy, который может быть мошенничеством, и я сомневаюсь, что этот метод самый быстрый, но это должно быть ясно. Он фильтрует логический массив, ссылаясь только на его индексы, и извлекает простые числа из индексов всех значений True. Не требуется по модулю.

import numpy as np
def ajs_primes3a(upto):
    mat = np.ones((upto), dtype=bool)
    mat[0] = False
    mat[1] = False
    mat[4::2] = False
    for idx in range(3, int(upto ** 0.5)+1, 2):
        mat[idx*2::idx] = False
    return np.where(mat == True)[0]

Answer 10

Самое быстрое простое сито в Pure Python :

def half_sieve(n):
    """
    Returns a list of prime numbers less than `n`.
    """
    if n <= 2:
        return []
    sieve = bytearray([True]) * (n // 2)
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i // 2]:
            sieve[i * i // 2::i] = bytearray((n - i * i - 1) // (2 * i) + 1)
    primes = list(compress(range(1, n, 2), sieve))
    primes[0] = 2
    return primes

Я оптимизировал Сито Эратосфена для скорости и памяти.

Benchmark

from time import clock
import platform

def benchmark(iterations, limit):
    start = clock()
    for x in range(iterations):
        half_sieve(limit)
    end = clock() - start
    print(f'{end/iterations:.4f} seconds for primes < {limit}')

if __name__ == '__main__':
    print(platform.python_version())
    print(platform.platform())
    print(platform.processor())
    it = 10
    for pw in range(4, 9):
        benchmark(it, 10**pw)

выход

>>> 3.6.7
>>> Windows-10-10.0.17763-SP0
>>> Intel64 Family 6 Model 78 Stepping 3, GenuineIntel
>>> 0.0003 seconds for primes < 10000
>>> 0.0021 seconds for primes < 100000
>>> 0.0204 seconds for primes < 1000000
>>> 0.2389 seconds for primes < 10000000
>>> 2.6702 seconds for primes < 100000000