Я хотел найти простые числа для математического приложения, которое я создаю, и наткнулся на подход Сита Эратосфена.
Я написал его реализацию на Python. Но это ужасно медленно. Скажем, если я хочу найти все простые числа меньше 2 миллионов. Это занимает > 20 минут. (Я остановил это на этом этапе). Как я могу ускорить это?
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)
ОБНОВЛЕНИЕ: В итоге я выполнил профилирование этого кода и обнаружил, что довольно много времени было потрачено на удаление элемента из списка. Вполне понятно, учитывая, что для поиска элемента приходится обходить весь список (в наихудшем случае), затем удалять его, а затем корректировать список (возможно, какая-то копия продолжается?). В любом случае, я удалил list вместо dictionary. Моя новая реализация -
defprimes_sieve1(limit): limitn = limit+1 primes = dict() for i inrange(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)
Переведено автоматически
Ответ 1
Вы не совсем правильно реализуете алгоритм:
В вашем первом примере primes_sieve не поддерживает список флагов простоты для включения / выключения (как в алгоритме), а вместо этого непрерывно изменяет размер списка целых чисел, что очень дорого: удаление элемента из списка требует сдвига всех последующих элементов на единицу вниз.
Во втором примере primes_sieve1 поддерживается словарь флагов простоты, что является шагом в правильном направлении, но оно перебирает словарь в неопределенном порядке и избыточно вычеркивает множители факторов (вместо только множителей простых чисел, как в алгоритме). Вы могли бы исправить это, отсортировав ключи и пропустив не простые числа (что уже делает процесс на порядок быстрее), но все равно гораздо эффективнее просто использовать список напрямую.
Правильный алгоритм (со списком вместо словаря) выглядит примерно так:
defprimes_sieve2(limit): a = [True] * limit # Initialize the primality list a[0] = a[1] = False
for (i, isprime) inenumerate(a): if isprime: yield i for n inrange(i*i, limit, i): # Mark factors non-prime a[n] = False
(Обратите внимание, что это также включает в себя алгоритмическую оптимизацию запуска не простой маркировки в квадрате простого числа (i*i) вместо его двойника.)
Ответ 2
deferatosthenes(n): multiples = [] for i inrange(2, n+1): if i notin multiples: print (i) for j inrange(i*i, n+1, i): multiples.append(j)
eratosthenes(100)
Ответ 3
Удаление из начала массива (списка) требует перемещения всех элементов после него вниз. Это означает, что удаление каждого элемента из списка таким образом, начиная с начала, является операцией O (n ^ 2).
Вы можете сделать это гораздо эффективнее с помощью наборов:
for i inrange(2, limitn): if not_prime[i]: continue for f in xrange(i*2, limitn, i): not_prime[f] = True
primes.append(i)
return primes
Ответ 4
Намного быстрее:
import time defget_primes(n): m = n+1 #numbers = [True for i in range(m)] numbers = [True] * m #EDIT: faster for i inrange(2, int(n**0.5 + 1)): if numbers[i]: for j inrange(i*i, m, i): numbers[j] = False primes = [] for i inrange(2, m): if numbers[i]: primes.append(i) return primes