在 Python 中检查一个数字是否是质数 [英] Checking if a number is a prime number in Python

问题描述

我写了下面的代码，它应该检查输入的数字是否是质数，但有一个我无法解决的问题:

I have written the following code, which should check if the entered number is a prime number or not, but there is an issue i couldn't get through:

def main():
    n = input("Please enter a number:")
    is_prime(n)

def is_prime(a):
    x = True 
    for i in (2, a):
            while x:
               if a%i == 0:
                   x = False
               else:
                   x = True
               
            
    if x:
        print("prime")
    else:
        print("not prime")
        
main()

如果输入的数字不是质数，它会显示非质数"，正如它应该的那样，但如果数字是质数，它不会显示任何内容.你能帮我吗?

If the entered number is not a prime number, it displays "not prime", as it is supposed to, but if the number is a prime number, it doesn't display anything. Could you please help me with it?

推荐答案

以下是我对这个问题的看法:

Here is my take on the problem:

from math import sqrt
from itertools import count, islice

def is_prime(n):
    return n > 1 and all(n % i for i in islice(count(2), int(sqrt(n)-1)))

这是一个非常简单和简洁的算法，因此它并不意味着接近最快或最优化的素性检查算法.它的时间复杂度为O(sqrt(n)).前往此处了解有关正确完成的素性测试及其历史的更多信息强>.

This is a really simple and concise algorithm, and therefore it is not meant to be anything near the fastest or the most optimal primality check algorithm. It has a time complexity of O(sqrt(n)). Head over here to learn more about primality tests done right and their history.

我会给你一些关于检查素数的几乎深奥的单行代码的内幕:

I'm gonna give you some insides about that almost esoteric single line of code that will check for prime numbers:

• 首先，在 Python 2 中使用 range() 确实是个坏主意，因为它会创建一个数字列表，这会占用大量内存.使用 xrange() 更好，因为它创建了一个 generator，它只需要记住你提供的初始参数，并即时生成每个数字.如果您正在使用Python 3，range() 默认已转换为生成器.顺便说一句，这仍然不是最好的解决方案:尝试为某些 n 调用 xrange(n) 使得 n >231-1(这是 C long 的最大值)引发 OverflowError.因此，创建范围生成器的最佳方法是使用 itertools:

• First of all, using range() in Python 2 is really a bad idea, because it will create a list of numbers, which uses a lot of memory. Using xrange() is better, because it creates a generator, which only needs to memorize the initial arguments you provide, and generates every number on-the-fly. If you're using Python 3, range() has been converted to a generator by default. By the way, this is still not the best solution: trying to call xrange(n) for some n such that n > 231-1 (which is the maximum value for a C long) raises OverflowError. Therefore the best way to create a range generator is to use itertools:

 xrange(2147483647+1) # OverflowError

 from itertools import count, islice

 count(1)                        # Count from 1 to infinity with step=+1
 islice(count(1), 2147483648)    # Count from 1 to 2^31 with step=+1
 islice(count(1, 3), 2147483648) # Count from 1 to 3*2^31 with step=+3

如果您想检查 n 是否为质数，实际上并不需要一直到 n.您可以显着减少测试，只检查从 2 到 √(n)(n 的平方根).举个例子:

You do not actually need to go all the way up to n if you want to check if n is a prime number. You can dramatically reduce the tests and only check from 2 to √(n) (square root of n). Here's an example:

让我们找出 n = 100 的所有除数，并将它们列在一个表中:

Let's find all the divisors of n = 100, and list them in a table:

 2  x  50 = 100
 4  x  25 = 100
 5  x  20 = 100
10  x  10 = 100 <-- sqrt(100)
20  x  5  = 100     
25  x  4  = 100
50  x  2  = 100

你很容易注意到，在n的平方根之后，我们找到的所有除数实际上都已经找到了.例如，20 已经被发现在执行 100/5.数字的平方根是我们发现的除数开始复制的确切中点.因此，要检查一个数是否为质数，您只需检查从 2 到 sqrt(n).

You will easily notice that, after the square root of n, all the divisors we find were actually already found. For example 20 was already found doing 100/5. The square root of a number is the exact mid-point where the divisors we found begin being duplicated. Therefore, to check if a number is prime, you'll only need to check from 2 to sqrt(n).

那么为什么是 sqrt(n)-1，而不仅仅是 sqrt(n)?那只是因为提供给 itertools.islice() 的第二个参数是要执行的迭代次数.islice(count(a), b) 在 b 次迭代后停止.这就是原因:

Why sqrt(n)-1 then, and not just sqrt(n)? That's just because the second argument provided to itertools.islice() is the number of iterations to execute. islice(count(a), b) stops after b iterations. That's the reason why:

 for number in islice(count(10), 2):
     print number,

 # Will print: 10 11

 for number in islice(count(1, 3), 10):
     print number,

 # Will print: 1 4 7 10 13 16 19 22 25 28

函数 all(...) 与以下内容相同:

 def all(iterable):
     for element in iterable:
         if not element:
             return False
     return True

它逐字地检查 iterable 中的所有元素，当它们中的任何一个评估为 False 时返回 False(对于整数意味着仅当它为零时).那我们为什么要使用它呢?首先，我们不需要使用额外的索引变量(就像我们使用循环所做的那样)，除此之外:只是为了简洁，没有真正需要它，但它看起来不那么笨重，只使用一行代码，而不是多行嵌套.

It literally checks for all the elements in the iterable, returning False when any of them evaluates to False (which for an integer means only if it's zero). Why do we use it then? First of all, we don't need to use an additional index variable (like we would do using a loop), other than that: just for concision, there's no real need of it, but it looks way less bulky to work with only a single line of code instead of several nested lines.

我包括一个未包装"的is_prime() 函数的版本，使其更易于理解和阅读:

I'm including an "unpacked" version of the is_prime() function, to make it easier to understand and read:

from math import sqrt
from itertools import count, islice

def is_prime(n):
    if n < 2:
        return False

    for number in islice(count(2), int(sqrt(n) - 1)):
        if n % number == 0:
            return False

    return True

这篇关于在 Python 中检查一个数字是否是质数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！