python - 测试素数的更短方法

Question

为了测试一个数字是否是素数，我这样做：

def isprime(n):

    if n < 2: return False

    for i in range(2, n):
        if n % i == 0:
            return False
    else:
        return True

我想知道如何使编写更有效/更短。

Answer 1

带发电机：

def isprime(n):
    return (all(False for i in range(2,n) if n % i == 0) and not n < 2)
    
print (isprime(0))
print (isprime(1))
print (isprime(2))
print (isprime(3))
print (isprime(9))
print (isprime(10))
print (isprime(13))

输出：

False
False
True
True
False
False
True

Answer 2

除了@Théophile 的建议，我还要添加以下建议：

1. 在调用之前测试一个数字是否为偶数且大于 2 is_prime（无需函数调用）。

2. 而不是range(2, n)，使用range(3, n, 2). 这将只考虑奇数；的第三个参数range是您将递增的步长。

3. 与其循环遍历小于 n 的平方根的所有整数（或所有奇数），不如创建一个已找到的素数缓存并循环遍历它们。执行此操作的最快和最优雅的方法之一是使用functools.lru_cache，但只需编写自己的缓存就足够了。

这是一种快速而肮脏的方法，比您的原始提议更长但更有效：

from math import sqrt

# We seed the cache with the first two odd primes because (1) it's low-
# hanging fruit and (2) we avoid the need to add extra lines of code (that
# will increase execution time) for cases in which the square roots of numbers
# are less than any primes in the list
odd_primes = [3, 5]

def is_prime(n):
    
    # If n is not prime, it must have at least one factor less than its square 
    # root.
    max_prime_factor_limit = int(sqrt(n))
    
    # use a generator here to avoid evaluating all the qualifying values in 
    # odd_primes until you need them. For example, the square root of 27 is
    # 5.1962, but, since it's divisible by 3, you'll only test if 27 is prime
    # one time. Not a big deal with smaller integers, but the time to compute
    # the next prime will increase pretty fast as there are more potential
    # factors.
    
    available_primes = (p for p in odd_primes if p <= max_prime_factor_limit)
    
    for prime in available_primes:
        if n % prime == 0:
            return False
    
    return True


for i in range(7, 99, 2):
    # if no prime factors were found, add to cache
    if is_prime(i):
        odd_primes.append(i)
        
print(odd_primes)

您可以做一些额外的事情来加快速度。立即浮现在脑海的是，不是计算您要检查的每个数字的平方根，而是使用素数的平方来确定您要检查的素数集的上限。换句话说，如果你知道 169 的平方是 13，那么你就知道任何大于 169 且小于 289（17 的平方）的数都有一个质因数 <= 13。你也可以用它来保存通过计算素数列表并将列表传递给您用来确定整数是否为素数的函数来计算时间。当然，请注意，这仅在您实际创建素数列表时才有效。

Answer 3

number = int(input('please enter a number:'))
if number>1:
    for numbers in range(2, number):
        if (number % numbers) ==0:
            print(f"{number} is not a prime number")
         
            break
    else:
        print(f"{number} is a prime number")  
else:
    print(f"{number} is not a prime number")