0

Hi all I have a question im working on in python and seem to be stuck on step 3 and 4. Any help would be great. This is the question:

Write a program which implements a function for the sieve of Eratosthenes. (http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes). The sieve of Eratosthenes is a simple algorithm for finding all prime numbers up to a specified integer. It was created by the ancient Greek mathematician Eratosthenes. The algorithm to find all the prime numbers less than or equal to a given integer n:

  1. Create a list of integers from two to n: 2, 3, 4, ..., n
  2. Start with a counter i set to 2, i.e. the first prime number
  3. Starting from i+i, count up by i and remove those numbers from the list, i.e. 2*i, 3*i, 4*i, and so on...
  4. Find the first number of the list following i. This is the next prime number.
  5. Set i to the number found in the previous step
  6. Repeat steps 3 and 4 until i is greater than n.
  7. All the numbers, which are still in the list, are prime numbers

This is what I have coded so far just don't know how to get the prime numbers from the list and remove the others....:

def main():    
    n = int(input("Enter a limiting number to find the prime numbers smaller than it: "))

    num_list = []
    num = 1
    for i in range(2, n + 1):
        num = num + 1
        num_list.append(num)

    i = 2
    for p in range(2, n):
        non_prime = num * i
        #while non_prime < n:
        if non_prime == num:
            num_list.remove(num)
    i = i + 1

    print(num_list)

main() # Call the main function

Thank for your help im banging my head against the wall as we speak.

4

2 回答 2

1

这是 wikipedia 上解释的算法的示例实现：

limit = 100
numbers = [_ for _ in range (2, limit + 1) ]
primes = []

while numbers:
    candidate = numbers [0]
    primes.append (candidate)
    for i in range (candidate, limit + 1, candidate):
        if i in numbers: numbers.remove (i)

print (primes)

解释：

  • numbers使用列表推导式进行初始化，2最多包含limit.

  • range (a, b, c)以 . 的步骤创建从auntil b（不包括）开始的数字c。

感谢 erewoks 的输入，这里有一个更详细的版本：

limit = 100
numbers = [_ for _ in range (2, limit + 1) ]
primes = []

while numbers:
    candidate = numbers [0]
    primes.append (candidate)
    factor = 1
    product = factor * candidate
    while product <= limit:
        if product in numbers: numbers.remove (product)
        factor += 1
        product = factor * candidate

print (primes)
于 2013-08-07T02:09:33.850 回答
0

使用 remove 的问题之一是筛子的主要优点是您不必去搜索列表中的数字。一个筛子可以编码如下

class Sieve(object):
    def __init__(self, limit):
        # step 1
        self.seive = [1] * limit
        # step 2
        self.index = 1
    def __next__(self):
        # step 4-5
        self.index += 1
        while self.index < len(self.seive) and not self.seive[self.index]:
            self.index += 1
        # step 6
        if self.index == len(self.seive):
            raise StopIteration
        # step 3
        for i in range(self.index ** 2, len(self.seive), self.index):
            self.seive[i] = 0
        return self.index
    def __iter__(self):
        return self
print(list(Sieve(100)))

列表是 self.seive=[1] * limit（步骤 1），然后我们设置 self.index=1（步骤 2），我们稍后将其递增，因此它将从 2 开始。

这些__iter__方法执行步骤 3-5，尽管从技术上讲，我们从步骤 5 开始，以找到我们没有划掉的下一个素数。然后我们划掉所有具有该因子的数字。

于 2013-08-07T02:39:12.823 回答