Попытка вычислить сито Eratosthenes

Question

Я абсолютный новичок в python, но я пытаюсь вычислить что-то, что должно действовать как сито Eratosthenes.

Я собираюсь начать легко и просто создать набор со всех целых чисел от 2 до 100. Давайте назовем, что набор С.

Затем я хочу, чтобы создать множество всех целых чисел п, что 2П содержащихся в этом множестве, назовем его P1. Другими словами, набор целых чисел 2, 4, 6, 8 и т. Д.

Я хочу сделать то же самое, но с P2 = 3n, а затем P3 = 5n.

В конце концов, я хочу вернуть все целые числа моего множества S, но не обращайте внимания на целые числа в P1, P2 и P3.

Как я буду продолжать это делать?

Моя попытка:

numbers=set(range(2,100)) 

, но я застрял на создании других наборов и пренебрегая их!

Спасибо.

Моя идея до сих пор:

def sieve(n): 
    S = set(range(2, 100)) 
    P1 = set(range(0, 100, 2)) 
    P2 = set(range(0, 100, 3)) 
    P3 = set(range(0, 100, 5)) 
    P5 = set(range(0, 100, 7)) 
    return S-P1-P2-P3-P5 
print (sieve(100)) 

Answer 1

Вот отрывок с ответом на ваш конкретный вопрос (не все сито):

S = set(range(2, 101)) #numbers 2 to 100 
P1 = set(range(2, 101, 2)) #2n 
P2 = set(range(3, 101, 3)) #3n 
P3 = set(range(5, 101, 5)) #5n 
print ('S = ', S) 
print ('P1 = ', P1) 
print ('P2 = ', P2) 
print ('P3 = ', P3) 
S = S - P1 - P2 - P3 #Here comes the "discarding" 
print ('S = ', S) 

Очевидно, что вы не хотите, чтобы ваши жёстко наборы Рх, и вы захотите определить следующий праймер, посмотрев на следующий недопустимый номер.

Answer 2

Функция range принимает третий параметр: шаг. Например, range(2, 10, 3) - [2, 5, 8]. Вы можете использовать это для построения множеств кратных некоторого числа, например. range(3, 100, 3) для кратных 3 меньше, чем 100, включая 3.

Объединить тех, с - оператором на множествах построить первый, наивный вариант решета:

p = set(range(2, 100)) 
for i in range(2, 10): 
    p = p - set(range(i, 100, i)) 
print sorted(p) 

Однако, это также удалить тестируемый i S themselved, таким образом, не хватает нескольких первых простых чисел:

[11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, ...] 

Исправление этого алгоритма остается в качестве упражнения для читателя. ;-)

Answer 3

могли бы попробовать это:

def filter_primes(alist, newlist): 
    for x in alist[1:]: 
     if x%alist[0] != 0: 
      newlist.append(x) 
    return newlist 

alist = range(2, 100) 
sieve_list = [] 
primes = [2] 

while len(alist) > 1: 
    a = filter_primes(alist, sieve_list) 
    primes.append(a[0]) 
    alist = sieve_list 
    sieve_list = [] 

print primes 

Out[1]: [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] 

Должно работать для любого числа, а не только 100.