Python实现判断位数较大的数字是否为质数

Question

我要判断100万个介于[5000000000, math.pow(2, 63) - 2]之间的随机数是否为质数，当我采用下面的写法时程序运行一下子就运行不下去了，请问问题在什么地方，我的算法哪里可以改进

def main():

    for k in range(1000000):
        num = random.randint(5000000000, math.pow(2, 63) - 2)
        # 质数大于 1
        if num > 1:
            # 查看因子
            for i in range(2, num):
                if (num % i) == 0:
                    print(num, "不是质数")
                    break
            else:
                print(num, "是质数")

        # 如果输入的数字小于或等于 1，不是质数
        else:
            print(num, "不是质数")

Answer 1

对于素性测试，目前无非有 2 种做法：确定性测试 和 随机性测试。

确定性测试就是可以给出确定性结果，但速度会比较慢。比如你使用的试除法以及其他回答给出的优化过的试除和筛选法。试除法比较适合去判定某个数的素性；而筛选法比较适合判定给定范围的数的素性。

而随机性测试并不能完全确定你要判断的数字的素性，而是有多大的概率为素数，但其速度较快。可以了解下 费马素性测试 和 拉宾米勒 素性测试等。这种方法比较适合用来判定一个大数的素性。

---

对于你的问题，100 万个在 [5000000000, math.pow(2, 63) - 2] 之间的数字，试除法会非常浪费时间。最好的解决方法是使用筛选法将 math.pow(2, 63) - 2 以下的素数全部筛选出来保存，然后再进行判断。具体做法其他答案也都说的差不多了，我就不再赘述

Answer 2

https://vv13.cn/posts/algorit...

Answer 3

稍作改进的版本, 如果保存一个大质数表可能会加快筛选速度

import random
import math

def main():

    for k in range(50):
        num = random.randint(5000000000, math.pow(2, 63) - 2)
        # 质数大于 1
        # 查看因子
        for i in range(2, int(math.sqrt(num))):
           if (num % i) == 0:
              print(num, "不是质数")
              break
                
        print(num, "是质数")


main()

Answer 4

素数筛

安装：pip install primesieve

import primesieve
from random import randint

n,m = 5e9, 2**63-2
p_itr = primesieve.Iterator()
i = 0
while i<10: #10个，找素数很耗时间和内存
    try:
        r = randint(n,m)
        p_itr.skipto(r)
        prm = p_itr.prev_prime()
        print(i, prm)
        i += 1
    except:
        continue

input('end')

结果：

0 3415627770444018089
1 2071501630625942117
2 1326985762033727
3 1065911183230293119
4 2371014087088275823
5 1829183457703024351
6 3266566713741763139
7 3351913961901458971
8 2028396891528291377
9 1968282757498824479
end

找素数很耗时间和内存，最好事先用primesieve生成100万个素数存到数据库里，然后随机选它们的编号即可。