Питон - Сито Эратосфена - Компактный Питон

Question

Это мой код для поиска простых чисел с помощью сита Эратосфена.

list = [i for i in range(2, int(raw_input("Compute primes up to what number? "))+1)]  

for i in list:
    for a in list:
            if a!=i and a%i == 0:
                list.remove(a)

Попытка найти способ сжать циклы, вложенные в цикл, в какой-то генератор или понимание, но не похоже, что вы можете применить функцию к списку, используя понимание. Я пытался использовать карту и фильтр, но я не могу понять, как это правильно.

Думая о чем-то вроде этого:

print map(list.remove(a), filter(lambda a, i: (a%i ==0 and a!=i), [(a, i) for i in list for a in list])

Очевидно, что не работает по дюжине причин. Если бы я только использовал часть фильтра этого кода:

filter(lambda a, i: (a%i ==0 and a!=i), **[(a, i) for i in list for a in list]**

Как правильно поместить две переменные в лямбду? (a, i) делает его кортежем, но я хочу представить «a» и «i» как независимые переменные для помещения в лямбду.

В итоге я решил проблему с помощью этой однострочной:

print sorted(set([i for i in range(2, int(raw_input("Compute primes up to what number? "))+1)]).difference(a for i in l for a in l if a!=i and a%i == 0))

Answer 1

Первое, на что нужно обратить внимание, это то, что вы написали не сито эратосфена. Посмотрите, сколько петель выполняет абсолютно наивное сито эратосфена:

def sieve1(n):
    loops = 0
    numbers = set(range(2, n))
    for i in range(2, int(n ** 0.5) + 1):
        for j in range(i * 2, n, i):
            numbers.discard(j)
            loops += 1
    return sorted(numbers), loops

Протестировано:

>>> sieve1(100)
([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], 
 178)

178 циклов на 100 номеров (не включая сортировку). Это может быть улучшено с небольшими изменениями:

def sieve2(n):
    loops = 0
    numbers = range(0, n)
    for prime in numbers:
        if prime < 2:
            continue
        elif prime > n ** 0.5:
            break
        for i in range(prime ** 2, n, prime):
            numbers[i] = 0
            loops += 1
    return [x for x in numbers if x > 1], loops

Протестировано:

>>> sieve2(100)
([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], 
 102)

102 петли для 100 номеров (не включая фильтр в конце). Теперь посмотри на свои:

def sieve3(n):
    loops = 0
    numbers = range(2, n)
    for i in numbers:
        for j in numbers:
            if j != i and j % i == 0:
                numbers.remove(j)
            loops += 1
    return numbers, loops

Протестировано:

>>> sieve3(100)
([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], 
 663)

Становится хуже:

>>> [sieve1(x)[1] for x in [100, 1000, 10000]]
[178, 2978, 41723]
>>> [sieve2(x)[1] for x in [100, 1000, 10000]]
[102, 1409, 16979]
>>> [sieve3(x)[1] for x in [100, 1000, 10000]]
[663, 28986, 1523699]

На n = 10000 ваша реализация выполняет почти в 100 раз больше!

Мое предложение состояло бы в том, чтобы создать разумную реализацию, прежде чем сделать ее "компактной". Кодовый гольф может быть увлекательным, но он далеко не так сложен или поучителен, как написание эффективного кода любой длины.

Тем не менее, рассмотрите эту однострочную строку (если не считать импорт, от которого можно избавиться, используя lambda x, y: x - y вместо operator.sub). Это реализует первый алгоритм с небольшим улучшением:

>>> from operator import sub
>>> reduce(sub, (set(range(x ** 2, 100, x)) for x in range(2, int(100 ** 0.5) + 1)), set(range(2, 100)))
set([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])

Answer 2

Это не совсем прямой перевод ваших циклов, но он довольно близок и компактен:

>>> l = range(2, 101)
>>> sorted(set(l).difference(a for i in l for a in l if a!=i and a%i == 0))
[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]

Хотя я бы предложил a > i вместо a != 0 как более короткий и быстрый;)

Answer 3

Ты не делаешь Сито Эратосфена;опасность неправильной реализации алгоритма состоит в том, что он будет очень медленным.Попробуйте свой алгоритм на 10**6, например.

Кратчайшая реализация ограниченного сита Эратосфена, которое я могу придумать:

def primes(upTo):
    isPrime = list(range(upTo))
    for p in range(2,int(upTo**0.5)+1): #p: 2,3,4,...,sqrt(N)
        print(p, isPrime[p])
        if isPrime[p]:
            for multiple in range(p**2,upTo,p): #mult: p^2, p^2+p, p^2+2p, ..., N
                isPrime[multiple] = False
    return [x for x in isPrime[2:] if x]

Демонстрация:

>>> list(primes(29))
[2, 3, 5, 7, 11, 13, 17, 19, 23]

Это на самом деле довольно лаконично, если вы игнорируете разрывы строк и массовую оптимизацию с пропуском четных чисел:

isPrime=[True]*upTo for p in range(2,upTo): if isPrime[p]: yield p for m in range(p,upTo,p): isPrime[m]=False

Answer 4

Не совсем самое компактное решение, но здесь помогает аргумент step в функции range в Python3 -

prime_sieve = [True] * (int(input('Primes Upto ?'))+1)
# The first prime number
for i in range(2, len(prime_sieve)):
    if prime_sieve[i]:
        for j in range(i+i, len(prime_sieve), i):
            prime_sieve[j] = False
        print(i, end=',')

Answer 5

Вот самое компактное настоящее сито, которое я когда-либо придумывал. Это работает на удивление хорошо.

def pgen(n): # Sieve of Eratosthenes generator
    np = set() # keeps track of composite (not prime) numbers
    for q in xrange(2, n+1):
        if q not in np:
            yield q
            np.update(range(q*q, n+1, q))

>>> list(pgen(100))
[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]            

Эта немного более сложная версия - самая быстрая, которую я видел:

def pgen(n): # Sieve of Eratosthenes generator by Dan Salmonsen
    yield 2
    np = set()
    for q in xrange(3, n+1, 2):
        if q not in np:
            yield q
            np.update(range(q*q, n+1, q+q))            

Вот истинное сито для понимания списка:

def primes(n):
    sieve = set(sum([range(q*q, n+1, q+q) for q in odds], []))
    return [2] + [p for p in odds if p not in sieve]

>>> primes(100)
[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]            

Answer 6

def sieve(n):
    sieve_list = range(n)
    zero_list = [0] * n
    for i in range(2, int(n**.5) + 1):
        if sieve_list[i]:
            sieve_list[2*i:n:i] = zero_list[2*i:n:i]
    return filter(None, sieve_list)[1:]

Answer 7

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

import itertools

def primes():
    ints = itertools.count(2)
    while True:
        p = next(ints)
        yield p
        ints = itertools.ifilter(p.__rmod__, ints)

print list(itertools.islice(primes(), 10))
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Answer 8

Следующая строка не связана с вашим кодом:

def primes(n):
    return set(range(2,n))-{c for i in range(2,n) for c in range(2*i,n,i)}

Как и ваш код, это все еще на самом деле Сито Эратосфена, потому что, например, он будет тщетно пытаться вычеркнуть кратные 6 и 9 и т. Д. Тем не менее, он все еще работает значительно быстрее, чем большинство других схожих с Sieve значений меньше миллиона или больше, поскольку для маленьких N простых чисел "примерно столько же, сколько простых чисел (доля простых чисел 1/log(N)).

Сильно изменен из источника, возможно, менее эффективен, чем оригинал: http://codeblog.dhananjaynene.com/2011/06/10-python-one-liners-to-impress-your-friends/