尝试计算Eratosthenes的筛子

我是python的绝对新手，但我试图计算一些应该像Eratosthenes的筛子那样的东西。尝试计算Eratosthenes的筛子

我要开始容易，只需创建一组与2的所有整数高达100让我们调用集合S

然后我想创建一个所有整数N个这样的2n是包含在该集合中，我们称之为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))

来源

2014-01-21 user3200098

尝试'范围（2，100，2）'，'范围（3，100， 3）'等等。第三个参数是这个步骤。 –

我该如何丢弃集合？ – user3200098

抽象集。 'S - P1'等。 – Hyperboreus

这里用回答您的具体问题的一个片段（不是整个筛）：

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)

显然，你不会想死您Px的套，并且您将希望通过查看下一个尚未存储的号码来识别下一个引物。

来源

2014-01-21 20:44:12 Hyperboreus

我的代码工作正常，直到我做了一个P4 =设置（范围（0，100，7）），然后整个序列被拧紧。怎么来的？是不是应该删除7,14,21等？ – user3200098

我把我的代码编辑到目前为止。 – user3200098

它应该是范围（7，100，7）而不是范围（0，100，7）。 – Hyperboreus

range函数接受第三个参数：该步骤。例如，range(2, 10, 3)是[2, 5, 8]。您可以使用它来构建一些数字的倍数集，例如range(3, 100, 3)为小于100的3的倍数，包括3本身。

结合那些与-操作上套建筛的第一，天真版本：

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

然而，这也将删除测试i s ^据为己有，因此缺乏前几个质数：

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

修复这个算法留给读者练习。 ;-)

来源

2014-01-21 20:44:22

可以试试这个：

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

来源

2014-01-22 19:37:21 gobrewers14

尝试计算Eratosthenes的筛子

回答

相关问题