097. 较大的非梅森素数(Large non-Mersenne prime)

第一个超过一百万位的素数是在1999年被发现的,它是一个具有\(2^{6972593}-1\)形式的梅森素数,它总共有\( 2,098,960\)位。之后更多的具有\(2^p-1\)形式的梅森素数被发现,并表包含更多的位数。然而,2004年人们发现了一个巨大的非梅森素数\(28433\times2^{7830457}+1\),它共有2,357,207位,求这个素数的最后十位数字。

分析:因为python支持大整数,不用担心溢出问题,所以我们可以直接计算这个质数,然后求它除以\(10^{10}\)的余数就可以了,得到的就是这个质数的最后十位数字。代码如下:

# ans = 8739992577, time cost = 5.15 µs

def main():
    res = (28433*pow(2,7830457,10**10)+1)%(10**10)
    return res