python中的素性测试 [英] Primality test in python

问题描述

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

I'm trying to do a simple primality test in Python.

根据维基百科，素性测试如下:

给定一个输入数n，检查2到n-1之间的任何整数m是否能整除n.如果 n 可以被任何 m 整除，则 n 是合数，否则是质数.

Given an input number n, check whether any integer m from 2 to n − 1 divides n. If n is divisible by any m then n is composite, otherwise it is prime.

我首先排除偶数 - 除了 2 - 作为素数的候选

I started with ruling out the even numbers - with the exception of 2 - as candidates to prime

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

然后根据上述规则编写一个函数来检查素数.

Then writing a function to check for primes, according to the rules above.

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

这是主要的函数，它迭代一个包含 8000 个素数候选者的列表并测试它们的素数

And this is the main function, which iterates over a list of 8000 prime candidates and tests their primality

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.

The problem is that the isprime function returns True for numbers that aren't primes.

推荐答案

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

In brief, your isprime(x) checks whether the number is odd, exiting right after if x % 2 == 0.

尝试一些小的更改，以便您真正进行迭代:

Try a small change so that you would actually iterate:

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

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

Note that else: is now part of the for loop rather than if statement.

这篇关于python中的素性测试的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！