Python 列表（带质数）

Question

我是 Python 的初学者，我需要帮助修复我创建的这段代码。 Bassicaly，我在下面有我的代码。

import math

def generate_p(p, Count, X, List):
    while Count <= X:
        isprime = True
        for x in range(2, int(math.sqrt(p)) + 1):
            if p % x == 0:
                isprime = False
        if isprime:
            Count += 1
            print p
            P.append(p)
        p += 1

if __name__ == "__main__":
    p = 2
    count = 1
    X = int(raw_input('number: '))
    List = []
    generate_p(p, count, X, List)

基本上，该功能确实有效，但是，它无法按照我希望的方式运行。首先，我将说明函数的逻辑是如何工作的，因为代码的第二部分只是变量和声明函数。
而变量 count 小于或等于 X，则 is prime 为真，只要 p（被测试的数字）可以无余数地进入每个 x（x 在 2 到 p 的平方根的范围内）。如果它是素数，则将 1 添加到计数中，打印素数，将其也添加到列表中，然后将 1 加到 p，即被测试的数字。如果它不是素数，则只需将 p 加 1。这一直持续到 Count 大于 X，然后代码停止。
正如您现在可能已经注意到的那样，有一个收集素数的列表，但是，这大部分未被使用。我想做的，但我不知道该怎么做，就是修复这部分代码，

for x in range(2, int(math.sqrt(p)) + 1):
    if p % x == 0:
        isprime = False

所以 x 在 2 和 p+1 的平方根的范围内，但是，我只希望 x 是 P 列表中该范围内的数字。任何人都可以帮我做这个，也许指出这段代码中的任何其他内容？

Answer 1

您可以使用 List Comprehension，像这样：

for x in [prime in P if prime<=math.sqrt(p)]:
    ...

Answer 2

如果您只想迭代 P 中小于或等于 p 的平方根的数字：

for x in (i for i in P if i <= math.sqrt(p)):
    if p % x == 0:
        isprime = False
        break # can stop here

请注意，将 p 和 P 作为变量非常混乱。

Answer 3

虽然其他答案在逻辑上是正确的，但他们会评估 P 中的每个项目的大小。如果 P 按大小升序排序，并且 P 足够大，那么只循环遍历 P 并在循环顶部包含一个 break 子句可能更有效。

Edit 实际上，要执行此操作，您需要将此部分拆分为它自己的函数，这样您就不会终止顶层 while 循环.然后你只需 return True/False 在每个点

def is_prime(x, P):
    sqrt_p = int(math.sqrt(p)) + 1
    for x in P:
        if x > sqrt_p:
            return True
        if p % x == 0:
            return False
    return True

在其他观察方面：

尝试使用更好的名称。 X、List、P、p 等使得代码难以调试和修改。事实上，您将 List 发送到函数中但不对其执行任何操作 - 我猜 P 和 List 应该是同一件事。使用 upper_bound、prime_list、prime 等名称更容易 mitigated/spotted 混淆变量。还要检查 PEP8 在 Python 中的一般命名约定，这将使您的代码对其他 Python 程序员更具可读性和一致性。
与其在函数外创建一个空列表，然后将其作为参数发送，不如在函数内创建列表，追加找到的所有素数，并让函数 return列表 - 它往往会提高可读性并减少错误的范围。

Answer 4

我认为您正在寻找 sieve of Eratosthenes 算法。 python 实现可能如下所示：

 def erato(n):
    "Compute all prime numbers less than or equal to n"
    # utility functions in order to work only with numbers starting at 2
    def prime(i):
        return isprime[i - 2]
    def setprime(i, val):
        isprime[i - 2] = val
    # suppose all numbers may be primes until we find divisors
    isprime = [ True for i in range(2, n+1) ]
    for i in range(2, int(math.sqrt(n)) + 1):
        # do not process non prime numbers
        if prime(i):
            # if i is prime, all its multiples are not
            j = 2 * i
            while j <= n :
                setprime(j, False)
                j += i
    # return the list of prime numbers
    return [ i for i in range(2, n + 1) if prime(i) ]

Answer 5

看看你能不能把面条绕在这个发电机上……最快的。

def isprime(value):
    stack = [0 for i in xrange(value*2)]
    for jump in xrange(2,value,1):
        for i in xrange(jump,value*2,jump):
            stack[i] += 1
    if stack[value] > 1:
        return False
    else:
        return True

至少是我最快的方法。比检查每个数字快得多

Answer 6

如果您想在 p 较大时针对时间复杂度优化函数，我建议您查看 Fermats 素数检验或 Soloway strausse 素数检验。此外，公因数列表可能会派上用场！

Python 列表（带质数）

Python List (with prime numbers)

python

primes