Генератор Python в однострочном

Ответ 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 ⁸ в то время как исходная мутирующая версия сдалась примерно на 10 ⁹ закончилась нехватка памяти ( странно).

Оригинальная версия reduce отказалась от 10 ⁷. Поэтому, возможно, это не так уж и неэффективно (по крайней мере, для номеров, с которыми вы можете иметь дело на своем компьютере).

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 ⁸ то же самое, что и однострочный мутирующий вариант.

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

Ответ 2

Вы не можете проверять продукты чисел только до квадратного корня, чтобы проверить на простое. Посмотрите на 8 - квадратный корень из 8 равен 2.8, поэтому он никогда не попробует 4 * 2. (Действительно, единственные числа, которые не будут рассматриваться как простые числа, являются квадратными числами).

ETA: вместо того, чтобы пытаться использовать все возможные комбинации j и k, почему бы не проверить, делится ли я каждым j (используя i % j == 0) до квадратного корня j? Это и делает меньше кода и намного эффективнее (хотя оно все еще не так эффективно, как сито Эратосфена).

Ответ 3

Здесь вы хотели:

def primes (q) :
 # return (i for i in xrange(2,q) if i not in [j*k for j in xrange(1,i) for k in xrange(1,i)])
 # return (i for i in xrange(2,q) if i not in [j*k for j in xrange(1,i) for k in xrange(1,j+1)])
 # return (i for i in xrange(2,q) if i not in [j*k for j in xrange(1,i/2+1) for k in xrange(1,j+1)])

 return (i for i in xrange(2,q) if i not in [j*k for j in xrange(1,i/2+1) for k in xrange(1,min(j+1,i/j+1))])

В Haskell диапазоны включены, поэтому primes(542)

[n | n<-[2..541], not $ elem n [j*k | j<-[1..n-1],     k<-[1..n-1]]]  --  25.66s
[n | n<-[2..541], not $ elem n [j*k | j<-[1..n-1],     k<-[1..j]]]    --  15.30s
[n | n<-[2..541], not $ elem n [j*k | j<-[1..n`div`2], k<-[1..j]]]    --   6.00s
                                                                      --   0.79s
[n | n<-[2..541], not $ elem n [j*k | j<-[1..n`div`2], k<-[1..min j (n`div`j)]]] 

И на самом деле, 1*x == x поэтому 1 не нужен как множитель, поэтому он должен быть

[n | n<-[2..541], not $ elem n [j*k | j<-[2..n`div`2], k<-[2..min j (n`div`j)]]] 

который занимает всего 0,59 секунды. Или, в Python,

def primes (q) :
 return (i for i in xrange(2,q) if i not in [j*k for j in xrange(2,i/2+1) for k in xrange(2,min(j+1,i/j+1))])

обновление: по какой-то причине min j ... не имеет большого значения, по крайней мере, в Haskell. Таким образом, выражение становится просто

[n | n<-[2..541], not $ elem n [j*k | j<-[2..n`div`2], k<-[2..n`div`j]]] 

Ответ 4

Как насчет:

def primes(x):
  return [i for i in range(2,x) if 0 not in [i%j for j in range(2,i)]]

Ответ 5

используя понимание

[x for x in range(4, 1000) if all(x % y != 0 for y in range(2, int(math.sqrt(x)) + 1))]