（Python）素数函数无限循环

Question

我现在正在研制一台超级计算机，把一个任务（找到质数）分配给其他机器。现在我在某个地方遇到了一个无限循环，我想我已经找到了素数函数，但不能确切地知道它在哪里。 我只对compsci感兴趣，所以非常感谢您的帮助。在

上界是LB的下界。在

谢谢！在

def do_work(self,LB,UB):

    msg = M_DATA
    initialdata = self.recv()
    n = UB
    p = 2
    total = 0


    for p in range(LB,UB):
        prime = True
        for i in range(2, p):
            if p % i == 0:
                prime = False
                break
        if prime == True:
            #print numbers found
            #print (p)
            total += 1

    return (total)

Answer 1

两个素数之间的距离增大，并且“趋向无穷大”。因此，对于相当大的LB，找到素数所需的迭代次数会变得足够大，看起来就像陷入了一个无限循环中。这就是为什么素数很难找到。在

你可以通过观察素数的定义来改进你的算法，而不需要做太多的改变。您不需要检查每个小于prime的整数的余数，而只需要检查小于sqrt(prime)的素数就可以给出明确的答案。以2为例：如果一个数不被2除，它就不会被偶数（4、6、8、10等）除。在

然后，您可以通过在外循环中使用range(UB, LB, 2)将所需的迭代次数减半，因为UB是奇数（即range(UB + (1 - (UB % 2), LB, 2)）。在

对于内部循环，存储一个找到的素数的列表，并在它低于sqrt(prime_to_check)时对其进行迭代。那会很有帮助的。在

Answer 2

你测试过这个功能了吗？有关从方法中提取的示例函数，请参见下文。如果不考虑它的效率和所有，它似乎没有一个无限循环，尽管你可以看到它的逻辑。在

#! /usr/bin/env python

def do_work(LB,UB):
    p = 2
    total = 0
    primes = []

    for p in range(LB,UB):
        prime = True
        for i in range(2, p):
            if p % i == 0:
                prime = False
                break
        if prime == True:
            #print numbers found
            primes.append(p)
            total += 1

    return LB, UB, total, primes

for i in xrange(100): print do_work(2, i)

有几件事需要注意：你有一些变量，比如msg，initialdata，n，它们没有被使用。返回语句有点奇怪。return (total,)将返回一个包含total的元组。return total只返回总数。在

M_数据和自我接收（）在这里是未知的，所以我冒昧地说，您可能有一个与之相关的无限循环。在