前言
前段时间在CINTA群讨论MSP(Modular Subset Product problem)的时候搞了个这样的程序，然后被@Bintou 问到“next_prime输入很大时跑半天都跑不出来”，试了一下，除了next_prime，random_prime也是这样。
于是水了篇帖子。。。
正文
这里我选择直接看Sage里next_prime和random_prime的代码是怎么实现的，先找random_prime的，介绍一个很chun但很实用的定位代码位置的方法：python报错的时候会显示报错代码的位置，所以随便输点会让random_prime报错的输入就好，比如字符串。
然后找到random_prime的实现大概如下：
def random_prime(n, proof=None, lbound=2):
... ...
if proof:
prime_test = is_prime
else:
prime_test = is_pseudoprime
randint = ZZ.random_element
while True:
# In order to ... ....
p = randint(lbound, n)
if prime_test(p):
return p
就是随机选一个lbound到n的数做素性测试，通过则返回，不通过则选另一个。这里注意到一个叫proof的参数，当proof是False的时候做的是伪素数(Pseudoprime)的测试（至于怎么测的和伪到什么程度，先留个坑...），伪素数的测试比素数的测试(指is_prime)快很多，所以做random_prime时，把第二个参数设成False，速度大大提升，问题解决，但生成的是伪素数。
next_prime同，第二个参数设False，生成伪素数，速度提升（next_prime的做法好像是先找下一个伪素数，然后再判断是不是真素数的，设False的话就不做真素数的判断，有兴趣可以自己看源码）
总结
加个False
