Ответ 1
Это не Сито Эратосфена, хотя оно похоже. На самом деле это намного хуже. Сито - лучший алгоритм поиска простых чисел.
См. http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
edit: я изменил fooobar.com/questions/14478/... как однострочный (первоначально это было не настоящее сито, но теперь это... возможно...):
reduce( (lambda r,x: r-set(range(x**2,N,x)) if (x in r) else r),
range(2,N), set(range(2,N)))
Демо:
>>> primesUpTo(N): lambda N: reduce(...)
>>> primesUpTo(30)
{2, 3, 5, 7, 11, 13, 17, 19}
К сожалению, я думаю, что, хотя это будет эффективно на функциональном языке программирования, оно может быть не столь эффективным в python из-за непостоянных (разделяемых и неизменных) структур данных, и любое сито в python должно будет использовать для достижения сопоставимых результатов. Мы все еще можем втиснуть его в один лайнер, если мы отчаянно хотели этого. Но сначала...
Нормальное сито:
>>> N = 100
>>> table = list(range(N))
>>> for i in range(2,int(N**0.5)+1):
... if table[i]:
... for mult in range(i**2,N,i):
... table[mult] = False
...
>>> primes = [p for p in table if p][1:]
>>> primes
[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]
Теперь мы можем определить и вызывать анонимные функции в одной строке, а также взломать [...].__setitem__ для выполнения встроенной мутации и взломать ... and foo для оценки ... при возврате foo:
>>> primesUpTo = lambda N: (lambda table: [[table.__setitem__(mult,False) for mult in range(i**2,N,i)] for i in range(2,int(N**0.5)+1) if table[i]] and [p for p in table if p][1:])(list(range(N)))
>>> primesUpTo(30)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Продолжайте съеживаться с ужасом, однострочный расширитель (странно красивый, потому что вы почти сразу можете перевести поток управления, но ужасное злоупотребление всем):
lambda N:
(lambda table:
[[table.__setitem__(mult,False) for mult in range(i**2,N,i)]
for i in range(2,int(N**0.5)+1) if table[i]]
and [p for p in table if p][1:]
)(list(range(N)))
Эта мутирующая версия с одним лайнером оставила на моей машине около 10 8 в то время как исходная мутирующая версия сдалась примерно на 10 9 закончилась нехватка памяти ( странно).
Оригинальная версия reduce отказалась от 10 7. Поэтому, возможно, это не так уж и неэффективно (по крайней мере, для номеров, с которыми вы можете иметь дело на своем компьютере).
edit2 Кажется, вы можете более грубо использовать побочные эффекты, например:
reduce( (lambda r,x: (r.difference_update(range(x**2,N,x)) or r)
if (x in r) else r),
range(2,N), set(range(2,N)))
Он дает около 10 8 то же самое, что и однострочный мутирующий вариант.
edit3: Этот работает в O (N) эмпирическая сложность, тогда как без difference_update она выполнялась при O (n ^ 2.2) сложности.
Ограничение диапазона, который уменьшен до уровня верхнего предела, и с коэффициентом только, оба приводят к дополнительной скорости -ups (соответственно 2x и 1.6x):
reduce( (lambda r,x: (r.difference_update(range(x*x,N,2*x)) or r)
if (x in r) else r),
range(3, int((N+1)**0.5+1), 2),
set([2] + range(3,N,2)))