在python中有没有一种快速有效的方法来检查一个数字是否是质数(10^18位)

Question

我一直在使用这个代码来检查一个数字是否为质数：

def pcheck(number):
    if number < 2:
        k = "NO"
    # theres no prime number less than 2
    else:
        i = 2
        factors = []
        while i * i <= number:
            if number % i:
                i += 1
            else:
                number //= i
                factors.append(i)
        if number > 1:
            factors.append(n)
        # get the factors of the number, a prime number will only have 1 factor, not including 1
        if len(factors) == 1:
            k = "YES"
        else:
            k = "NO"
    return k


n = int(input())
print(pcheck(n))

但即使有修改，它仍然与18位数的数字斗争，这对我来说是相当麻烦的，因为我不能在这种情况下使用它。我听说过rabin miller测试，但从未能够在我的代码中实现它。有没有一种更有效的方法来检查大数的素数，但仍然尽可能快？

Answer 1

有很多方法可以改进这个功能。首先，您只需检查直到number的平方根，以确定您是否会找到任何有意义的因子。而且，一旦你找到了一个因子，你就可以立即终止这个函数(你不需要一直搜索)。

不过，一般来说，没有快速的方法来做到这一点。这是一种质数的美。要知道一个大数是否为质数，需要花费大量的计算时间。它也需要大量的计算时间来寻找大量的素因数。