Еще один подход к возврату значения из асинхронной функции - передать объект, который сохранит результат от асинхронной функции.
Вот пример того же:
var async = require("async");
// This wires up result back to the caller
var result = {};
var asyncTasks = [];
asyncTasks.push(function(_callback){
// some asynchronous operation
$.ajax({
url: '...',
success: function(response) {
result.response = response;
_callback();
}
});
});
async.parallel(asyncTasks, function(){
// result is available after performing asynchronous operation
console.log(result)
console.log('Done');
});
Я использую объект result
для хранения значения во время асинхронной операции. Это позволяет получить результат даже после асинхронного задания.
Я использую этот подход много. Мне было бы интересно узнать, насколько хорошо этот подход работает, когда задействован результат обратно через последовательные модули.
Самый быстрый метод, который я пробовал до сих пор, основан на функции кулинарной книги Python 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
См. этот ответ для объяснения ускорения.
Связанный с этим вопрос (посвященный генераторам простых чисел и в том числе эталонам): Ускорение битстронных / битовых операций в Python?
Для быстрой версии python 3 см. код Bruno Astrolino: https://stackoverflow.com/a/46635266/350331
Faster & amp; более чистый код Python с памятью:
def primes(n):
""" Returns a list of primes < n """
sieve = [True] * n
for i in xrange(3,int(n**0.5)+1,2):
if sieve[i]:
sieve[i*i::2*i]=[False]*((n-i*i-1)/(2*i)+1)
return [2] + [i for i in xrange(3,n,2) if sieve[i]]
или начиная с половины сита
def primes1(n):
""" Returns a list of primes < n """
sieve = [True] * (n/2)
for i in xrange(3,int(n**0.5)+1,2):
if sieve[i/2]:
sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1)
return [2] + [2*i+1 for i in xrange(1,n/2) if sieve[i]]
Faster & amp; более объемный код с памятью:
import numpy
def primesfrom3to(n):
""" Returns a array of primes, 3 <= p < n """
sieve = numpy.ones(n/2, dtype=numpy.bool)
for i in xrange(3,int(n**0.5)+1,2):
if sieve[i/2]:
sieve[i*i/2::i] = False
return 2*numpy.nonzero(sieve)[0][1::]+1
- более быстрое изменение, начиная с трети сита:
import numpy
def primesfrom2to(n):
""" Input n>=6, Returns a array of primes, 2 <= p < n """
sieve = numpy.ones(n/3 + (n%6==2), dtype=numpy.bool)
for i in xrange(1,int(n**0.5)/3+1):
if sieve[i]:
k=3*i+1|1
sieve[ k*k/3 ::2*k] = False
sieve[k*(k-2*(i&1)+4)/3::2*k] = False
return numpy.r_[2,3,((3*numpy.nonzero(sieve)[0][1:]+1)|1)]
Версия с чистым питоном A (жесткий код) из вышеприведенного кода будет:
def primes2(n):
""" Input n>=6, Returns a list of primes, 2 <= p < n """
n, correction = n-n%6+6, 2-(n%6>1)
sieve = [True] * (n/3)
for i in xrange(1,int(n**0.5)/3+1):
if sieve[i]:
k=3*i+1|1
sieve[ k*k/3 ::2*k] = [False] * ((n/6-k*k/6-1)/k+1)
sieve[k*(k-2*(i&1)+4)/3::2*k] = [False] * ((n/6-k*(k-2*(i&1)+4)/6-1)/k+1)
return [2,3] + [3*i+1|1 for i in xrange(1,n/3-correction) if sieve[i]]
К сожалению, чистый-питон не использует более простой и более быстрый способ выполнения задания Assignment, а вызов len () внутри цикла, как и в [False]*len(sieve[((k*k)/3)::2*k])
, тоже медленный. Поэтому мне пришлось импровизировать, чтобы исправить ввод (и избежать большей математики) и сделать некоторую экстремальную (и больную) математическую магию. Лично я считаю, что стыдно, что numpy (который так широко используется) не является частью стандартной библиотеки python (через 2 года после версии python 3 и без совместимости с numpy), и что улучшения в синтаксисе и скорости, похоже, полностью игнорируются разработчиками python.
Я знаю, что конкурс закрыт на несколько лет. ...
Тем не менее это мое предложение для чистого простого сита python, основанного на исключении кратных 2, 3 и 5 с помощью соответствующих шагов при обработке сита вперёд. Тем не менее, это на самом деле медленнее для N & lt; 10 ^ 9, чем @Robert William Hanks превосходные решения rwh_primes2 и rwh_primes1. С помощью массива ctypes.c_ushort выше 1.5 * 10 ^ 8 он каким-то образом адаптируется к ограничениям памяти.
10 ^ 6
$ python -mtimeit -s "import primeSieveSpeedComp" " PrimeSieveSpeedComp.primeSieveSeq (1000000) "10 циклов, лучше всего 3: 46,7 мсек за цикл
для сравнения: $ python -mtimeit -s" import primeSieveSpeedComp "" primeSieveSpeedComp.rwh_primes1 (1000000) "10 петли, лучше всего 3: 43,2 мсек за цикл для сравнения: $ python -m timeit -s "import primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes2 (1000000)" 10 циклов, лучше всего 3: 34,5 мсек за цикл
blockquote >10 ^ 7
$ python -mtimeit -s "import primeSieveSpeedComp" "primeSieveSpeedComp.primeSieveSeq (10000000)" 10 циклов, лучше всего 3: 530 мсек за цикл
для сравнения: $ python -mtimeit -s "import primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes1 (10000000)" 10 циклов, лучше всего 3: 494 мсек за цикл для сравнения: $ python -m timeit -s "import primeSieveSpeedComp" " primeSieveSpeedComp.rwh_primes2 (+100000 00) «10 циклов, лучше всего 3: 375 мсек за цикл
blockquote>10 ^ 8
$ python -mtimeit -s" import primeSieveSpeedComp "" primeSieveSpeedComp.primeSieveSeq ( 100000000) «10 циклов, лучше всего 3: 5,55 сек за цикл
для сравнения: $ python -mtimeit -s" import primeSieveSpeedComp "" primeSieveSpeedComp.rwh_primes1 (100000000) "10 циклов, лучший из 3: 5,33 с за цикл для сравнения: $ python -m timeit -s "import primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes2 (100000000)" 10 циклов, лучше всего 3: 3,95 с за цикл
blockquote>10 ^ 9
$ python -mtimeit -s "import primeSieveSpeedComp" "primeSieveSpeedComp.primeSieveSeq (1000000000)" 10 циклов, лучше всего 3: 61,2 сек за цикл
to Сравнение: $ python -mtimeit -n 3 -s "import primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes1 (1000000000)" 3 петли, лучше всего 3: 97,8 сек за цикл
для сравнения: $ python -m timeit - s "import primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes2 (1000000000)" 10 петель, лучше всего 3: 41,9 сек за цикл
blockquote>Вы можете скопировать код ниже в ubuntus primeSieveSpeedComp, чтобы просмотреть эти тесты.
def primeSieveSeq(MAX_Int): if MAX_Int > 5*10**8: import ctypes int16Array = ctypes.c_ushort * (MAX_Int >> 1) sieve = int16Array() #print 'uses ctypes "unsigned short int Array"' else: sieve = (MAX_Int >> 1) * [False] #print 'uses python list() of long long int' if MAX_Int < 10**8: sieve[4::3] = [True]*((MAX_Int - 8)/6+1) sieve[12::5] = [True]*((MAX_Int - 24)/10+1) r = [2, 3, 5] n = 0 for i in xrange(int(MAX_Int**0.5)/30+1): n += 3 if not sieve[n]: n2 = (n << 1) + 1 r.append(n2) n2q = (n2**2) >> 1 sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1) n += 2 if not sieve[n]: n2 = (n << 1) + 1 r.append(n2) n2q = (n2**2) >> 1 sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1) n += 1 if not sieve[n]: n2 = (n << 1) + 1 r.append(n2) n2q = (n2**2) >> 1 sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1) n += 2 if not sieve[n]: n2 = (n << 1) + 1 r.append(n2) n2q = (n2**2) >> 1 sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1) n += 1 if not sieve[n]: n2 = (n << 1) + 1 r.append(n2) n2q = (n2**2) >> 1 sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1) n += 2 if not sieve[n]: n2 = (n << 1) + 1 r.append(n2) n2q = (n2**2) >> 1 sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1) n += 3 if not sieve[n]: n2 = (n << 1) + 1 r.append(n2) n2q = (n2**2) >> 1 sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1) n += 1 if not sieve[n]: n2 = (n << 1) + 1 r.append(n2) n2q = (n2**2) >> 1 sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1) if MAX_Int < 10**8: return [2, 3, 5]+[(p << 1) + 1 for p in [n for n in xrange(3, MAX_Int >> 1) if not sieve[n]]] n = n >> 1 try: for i in xrange((MAX_Int-2*n)/30 + 1): n += 3 if not sieve[n]: r.append((n << 1) + 1) n += 2 if not sieve[n]: r.append((n << 1) + 1) n += 1 if not sieve[n]: r.append((n << 1) + 1) n += 2 if not sieve[n]: r.append((n << 1) + 1) n += 1 if not sieve[n]: r.append((n << 1) + 1) n += 2 if not sieve[n]: r.append((n << 1) + 1) n += 3 if not sieve[n]: r.append((n << 1) + 1) n += 1 if not sieve[n]: r.append((n << 1) + 1) except: pass return r
Я предполагаю, что самый быстрый всех способов - это жестко кодировать простые числа в вашем коде.
Итак, почему бы просто не написать медленный скрипт, который генерирует другой исходный файл, который имеет все номера в нем, а затем импортирует этот исходный файл при запуске вашей реальной программы.
Конечно, это работает, только если вы знаете верхнюю границу N во время компиляции, но, таким образом, это так для (почти) всех проектных задач Эйлера.
& nbsp;
PS: Возможно, я ошибаюсь, хотя разбор источника с проводными штрихами медленнее, чем вычисление их в первую очередь, но насколько я знаю Python запускается из скомпилированных файлов .pyc
, поэтому чтение двоичного массива со всеми штрихами до N должно быть быстрым в этом случае.
Я медленно отвечаю на этот вопрос, но это было похоже на забавное упражнение. Я использую 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]
Вот интересный метод генерации простых чисел (но не самый эффективный) с использованием списков 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]
Здесь вы можете найти пример и некоторые объяснения здесь
Вот две обновленные (чистые версии Python 3.6) одной из самых быстрых функций,
from itertools import compress
def rwh_primes1v1(n):
""" Returns a list of primes < n for n > 2 """
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)
return [2,*compress(range(3,n,2), sieve[1:])]
def rwh_primes1v2(n):
""" Returns a list of primes < n for n > 2 """
sieve = bytearray([True]) * (n//2+1)
for i in range(1,int(n**0.5)//2+1):
if sieve[i]:
sieve[2*i*(i+1)::2*i+1] = bytearray((n//2-2*i*(i+1))//(2*i+1)+1)
return [2,*compress(range(3,n,2), sieve[1:])]
Я могу опоздать на вечеринку, но для этого мне придется добавить свой собственный код. Он использует приблизительно n / 2 в пространстве, потому что нам не нужно хранить четные числа, и я также использую модуль python bitarray, дополнительно сокращая потребление памяти и позволяя вычислять все простые числа до 1 000 000 000
from bitarray import bitarray
def primes_to(n):
size = n//2
sieve = bitarray(size)
sieve.setall(1)
limit = int(n**0.5)
for i in range(1,limit):
if sieve[i]:
val = 2*i+1
sieve[(i+i*val)::val] = 0
return [2] + [2*i+1 for i, v in enumerate(sieve) if v and i > 0]
python -m timeit -n10 -s "import euler" "euler.primes_to(1000000000)"
10 loops, best of 3: 46.5 sec per loop
Это было выполнено на 64-битном 2.4GHZ MAC OSX 10.8.3
Поучительно писать свой собственный код первичного поиска, но также полезно иметь быструю надежную библиотеку под рукой. Я написал обертку вокруг библиотеки C ++ primesieve , назвал ее primesieve-python
Попробуйте pip install primesieve
import primesieve
primes = primesieve.generate_primes(10**8)
Мне было бы любопытно увидеть скорость сравнения.
Для самого быстрого кода решение numpy является лучшим. Однако по чисто академическим причинам я публикую мою чистую версию python, которая немного меньше, чем на 50% быстрее, чем версия поваренной книги, опубликованная выше. Поскольку я делаю весь список в памяти, вам нужно достаточно места для хранения всего, но оно, кажется, масштабируется довольно хорошо.
def daniel_sieve_2(maxNumber):
"""
Given a number, returns all numbers less than or equal to
that number which are prime.
"""
allNumbers = range(3, maxNumber+1, 2)
for mIndex, number in enumerate(xrange(3, maxNumber+1, 2)):
if allNumbers[mIndex] == 0:
continue
# now set all multiples to 0
for index in xrange(mIndex+number, (maxNumber-3)/2+1, number):
allNumbers[index] = 0
return [2] + filter(lambda n: n!=0, allNumbers)
И результаты:
>>>mine = timeit.Timer("daniel_sieve_2(1000000)",
... "from sieves import daniel_sieve_2")
>>>prev = timeit.Timer("get_primes_erat(1000000)",
... "from sieves import get_primes_erat")
>>>print "Mine: {0:0.4f} ms".format(min(mine.repeat(3, 1))*1000)
Mine: 428.9446 ms
>>>print "Previous Best {0:0.4f} ms".format(min(prev.repeat(3, 1))*1000)
Previous Best 621.3581 ms
Если у вас есть контроль над N, самый быстрый способ перечислить все простые числа - это прекомпилировать их. Шутки в сторону. Предкомпиляция - это способ, который не учитывается при оптимизации.
Если вы принимаете itertools, но не numpy, вот адаптация rwh_primes2 для Python 3, которая работает на моей машине примерно в два раза быстрее. Единственным существенным изменением является использование bytearray вместо списка для логического и использование сжатия вместо понимания списка для создания окончательного списка. (Я бы добавил это как комментарий, например moarningsun, если бы я был в состоянии.)
import itertools
izip = itertools.zip_longest
chain = itertools.chain.from_iterable
compress = itertools.compress
def rwh_primes2_python3(n):
""" Input n>=6, Returns a list of primes, 2 <= p < n """
zero = bytearray([False])
size = n//3 + (n % 6 == 2)
sieve = bytearray([True]) * size
sieve[0] = False
for i in range(int(n**0.5)//3+1):
if sieve[i]:
k=3*i+1|1
start = (k*k+4*k-2*k*(i&1))//3
sieve[(k*k)//3::2*k]=zero*((size - (k*k)//3 - 1) // (2 * k) + 1)
sieve[ start ::2*k]=zero*((size - start - 1) // (2 * k) + 1)
ans = [2,3]
poss = chain(izip(*[range(i, n, 6) for i in (1,5)]))
ans.extend(compress(poss, sieve))
return ans
Сравнения:
>>> timeit.timeit('primes.rwh_primes2(10**6)', setup='import primes', number=1)
0.0652179726976101
>>> timeit.timeit('primes.rwh_primes2_python3(10**6)', setup='import primes', number=1)
0.03267321276325674
и
>>> timeit.timeit('primes.rwh_primes2(10**8)', setup='import primes', number=1)
6.394284538007014
>>> timeit.timeit('primes.rwh_primes2_python3(10**8)', setup='import primes', number=1)
3.833829450302801
Используя сито Сундарама , я думаю, что я сломал запись чистого Python:
def sundaram3(max_n):
numbers = range(3, max_n+1, 2)
half = (max_n)//2
initial = 4
for step in xrange(3, max_n+1, 2):
for i in xrange(initial, half, step):
numbers[i-1] = 0
initial += 2*(step+1)
if initial > half:
return [2] + filter(None, numbers)
Сравнение:
C:\USERS>python -m timeit -n10 -s "import get_primes" "get_primes.get_primes_erat(1000000)"
10 loops, best of 3: 710 msec per loop
C:\USERS>python -m timeit -n10 -s "import get_primes" "get_primes.daniel_sieve_2(1000000)"
10 loops, best of 3: 435 msec per loop
C:\USERS>python -m timeit -n10 -s "import get_primes" "get_primes.sundaram3(1000000)"
10 loops, best of 3: 327 msec per loop
Для действительно быстрого решения с достаточно большим N было бы загрузить предварительно просчитанный список простых чисел , сохранить его как кортеж и сделать что-то вроде:
for pos,i in enumerate(primes):
if i > N:
print primes[:pos]
Если N > primes[-1]
только , тогда вычисляйте больше простых чисел и сохраняем новый список в вашем коде, так что в следующий раз он будет столь же быстрым.
Всегда думайте, что нестандартно.
Все написано и протестировано. Таким образом, нет необходимости изобретать колесо.
python -m timeit -r10 -s"from sympy import sieve" "primes = list(sieve.primerange(1, 10**6))"
дает нам рекордный разрыв 12,2 мс!
10 loops, best of 10: 12.2 msec per loop
Если это не достаточно быстро, вы можете попробовать PyPy:
pypy -m timeit -r10 -s"from sympy import sieve" "primes = list(sieve.primerange(1, 10**6))"
, в результате чего:
10 loops, best of 10: 2.03 msec per loop
Ответ с 247 списками голосов для 15,9 мс для лучшего решения. Сравните это !!!
Вот код, который я обычно использую для генерации простых чисел в Python:
$ python -mtimeit -s'import sieve' 'sieve.sieve(1000000)'
10 loops, best of 3: 445 msec per loop
$ cat sieve.py
from math import sqrt
def sieve(size):
prime=[True]*size
rng=xrange
limit=int(sqrt(size))
for i in rng(3,limit+1,+2):
if prime[i]:
prime[i*i::+i]=[False]*len(prime[i*i::+i])
return [2]+[i for i in rng(3,size,+2) if prime[i]]
if __name__=='__main__':
print sieve(100)
Он не может конкурировать с более быстрыми решениями, размещенными здесь, но по крайней мере это чистый питон.
Спасибо, что опубликовал этот вопрос. Сегодня я многому научился.
Это можно сравнить с другими.
# 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
Так просто ...
Немного отличается реализация половинного сита с помощью Numpy:
import math import numpy def prime6(upto): primes=numpy.arange(3,upto+1,2) isprime=numpy.ones((upto-1)/2,dtype=bool) for factor in primes[:int(math.sqrt(upto))]: if isprime[(factor-2)/2]: isprime[(factor*3-2)/2:(upto-1)/2:factor]=0 return numpy.insert(primes[isprime],0,2)
Может ли кто-то сравнить это с другими таймингами? На моей машине это кажется довольно сопоставимым с другим полурешеткой Numpy.
В общем случае, если вам нужно быстрое вычисление числа, python не лучший выбор. Сегодня существует много более быстрого (и сложного) алгоритма. Например, на моем компьютере я получил 2,2 секунды для вашего кода, а Mathematica получил 0.088005.
Прежде всего: вам нужно установить?
Детерминированная реализация теста Первичности Миллера-Рабина в предположении, что N & lt; 9,080,191
import sys
import random
def miller_rabin_pass(a, n):
d = n - 1
s = 0
while d % 2 == 0:
d >>= 1
s += 1
a_to_power = pow(a, d, n)
if a_to_power == 1:
return True
for i in xrange(s-1):
if a_to_power == n - 1:
return True
a_to_power = (a_to_power * a_to_power) % n
return a_to_power == n - 1
def miller_rabin(n):
for a in [2, 3, 37, 73]:
if not miller_rabin_pass(a, n):
return False
return True
n = int(sys.argv[1])
primes = [2]
for p in range(3,n,2):
if miller_rabin(p):
primes.append(p)
print len(primes)
Согласно статье в Википедии ( http://en.wikipedia.org/wiki/Miller-Rabin_primality_test ) тестирование N & lt; 9,080,191 для a = 2,3,37 и 73 достаточно, чтобы решить, является ли N составным или нет.
И я адаптировал исходный код из вероятностной реализации оригинального теста Миллера-Рабина, найденного здесь: http://en.literateprograms.org/Miller-Rabin_primality_test_ (Python)
Для Python 3
def rwh_primes2(n):
correction = (n%6>1)
n = {0:n,1:n-1,2:n+4,3:n+3,4:n+2,5:n+1}[n%6]
sieve = [True] * (n//3)
sieve[0] = False
for i in range(int(n**0.5)//3+1):
if sieve[i]:
k=3*i+1|1
sieve[ ((k*k)//3) ::2*k]=[False]*((n//6-(k*k)//6-1)//k+1)
sieve[(k*k+4*k-2*k*(i&1))//3::2*k]=[False]*((n//6-(k*k+4*k-2*k*(i&1))//6-1)//k+1)
return [2,3] + [3*i+1|1 for i in range(1,n//3-correction) if sieve[i]]
С течением времени я собрал несколько простейших сит. Самый быстрый на моем компьютере следующий:
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
Алгоритм работает быстро, но имеет серьезный недостаток:
>>> sorted(get_primes(530))
[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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163,
167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251,
257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443,
449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 527, 529]
>>> 17*31
527
>>> 23*23
529
Вы предполагаете, что numbers.pop()
вернет наименьшее число в наборе, но это не гарантируется вообще. Наборы неупорядочены, а pop()
удаляет и возвращает произвольный элемент, поэтому его нельзя использовать для выбора следующего простого числа из оставшихся чисел.
Извините за беспокойство, но erat2 () имеет серьезный недостаток в алгоритме.
При поиске следующего композита нам нужно проверить только нечетные числа. q, p оба нечетны; то q + p четно и не нуждается в проверке, но q + 2 * p всегда нечетно. Это исключает проверку «если даже» в условиях цикла while и экономит около 30% времени выполнения.
Пока мы находимся в этом: вместо элегантного «D.pop (q, None)», get и delete использовать метод ', если q в 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
Это элегантное и более простое решение для поиска простых чисел с использованием сохраненного списка. Начинается с 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