输入大数并检查它是否为质数 (Python)

Question

我正在使用 python 制作一个程序，其中它会检查大数是否为质数。（这是用于 RSA 加密）

这是我的代码：

p = int(input("Enter first prime number: "))

while(1):
    if isPrime(p) is False:
        print("%d is not a prime number!" % p)
        p = int(input("Please enter first prime number again: "))
    else:
        print("%d is a prime number." % p)
        break

q = int(input("Enter second prime number: "))

while(1):
    if isPrime(q) is False:
        print("%d is not a prime number!" % q)
        q = int(input("Please enter second prime number again: "))
    else:
        print("%d is a prime number." % q)
        break

p是第一个大数，q是第二个大数。

这是检查它是否为质数的函数：

def isPrime(num):

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

我尝试运行使用 17 和 11 之类的小数字输入它并且它有效，但是当我尝试输入 16 位数字时，它不再起作用。

示例如下运行：

在第二张图上，当我输入一个大数字时，它没有继续。我试着等了半个小时，看看它是否有效，但它仍然是这样。为什么会这样？

Answer 1

之所以要花这么长时间，是因为您要遍历很多数字，每个数字直到 16 位数字，这是很多循环迭代。即使您只是在每次迭代中不断地工作，处理那么多数字仍然需要一段时间。 python 中的循环是出了名的慢。幸运的是，您可以像这样使用 sympy：

from sympy.ntheory import factorint
def isPrime(n):
    return len(factorint(n)) == 1

然后事情应该会进展得更快。供参考：

factorint(133453565475464563453)

花了大约半秒

输入大数并检查它是否为质数 (Python)

Inputting large numbers and check if it is prime (Python)

python

rsa