首页 文章

python中的Primality测试[重复]

提问于
浏览 次
7

这个问题在这里已有答案：

我正在尝试在Python中进行简单的素性测试 .

根据维基百科，primality test如下：

给定输入数n，检查从2到n - 1的任何整数m是否除以n . 如果n可以被任何m整除，则n是复合的，否则它是素数 .

我开始排除偶数 - 除了2 - 作为准备的候选人

def prime_candidates(x):
    odd = range(1, x, 2)
    odd.insert(0, 2)
    odd.remove(1)
    return odd

然后根据上面的规则编写一个函数来检查质数 .

def isprime(x):
    for i in range(2, x-1):
            if x % i == 0:
                    return False
            else:
                    return True

这是主要功能，它迭代8000个主要候选人的列表并测试他们的素数

def main():
    end = 8000
    candidates = prime_candidates(end)
    for i in candidates:
            if isprime(i) and i < end:
                    print 'prime found ' + str(i)

问题是 isprime 函数对于非素数的数字返回True .

python primes

4 回答

  • 8

    简而言之， isprime(x) 检查数字是否为奇数，在 if x % 2 == 0 之后立即退出 .

    尝试一个小的更改，以便您实际迭代：

    def isprime(x):
    for i in range(2, x-1):
        if x % i == 0:
            return False
    else:
        return True

    请注意 else: 现在是 for 循环的一部分而不是 if 语句 .

    回复于
  • 8

    如果概率算法足够，请查看Miller–Rabin primality test . 你也可以证明一个数字是素数，例如Elliptic Curve Primality Proving (ECPP)，但它需要更多的努力 .

    一个简单的试验分割算法如下

    def prime(a):
     return not (a < 2 or any(a % x == 0 for x in range(2, int(a ** 0.5) + 1)))

    Edit: 这是一个更具教育意义的版本，因为第一个解决方案非常简洁，可能更难阅读：

    from math import sqrt
def prime(a):
    if a < 2: return False
    for x in range(2, int(sqrt(a)) + 1):
        if a % x == 0:
            return False
    return True

    我用 sqrt(a) 代替 a ** 0.5 代替了事情 . 平方根用于不查看比我们更多的因素 .

    回复于
  • 2

    您的函数实际返回您的数字是否为奇数 .

    实际上，你正在做的是检查2是否除以你的号码，然后立即返回 . 你永远不会检查其他数字 .

    你需要做的是从if的else子句和for循环返回主函数体中返回true .

    在旁注中，如果您正在寻找低于给定数字的素数，您可以存储在内存中找到的素数，然后只尝试将新数除以这些素数！ （因为如果d是复合的并且除q，那么p存在使得p是素数而p除以q） .

    回复于
  • 2

    问题是你将 return False 放在 else 子句中而不是函数的末尾 . 因此，在检查第一个除数后，您的函数将立即返回，而不是继续检查其他除数 .

    这是一个类似于你的简单素性测试：

    def is_prime(n):
    d = 2
    while d * d <= n:
        if n % d == 0:
            return False
        d += 1
    return n > 1
    回复于

相关问题