@jasl @paranoyang N 的量级是 20 的几十次方,比如 20 的 20 次方是 104857600000000000000000000,使用筛选法,相当于要把这些个数字都存下来,不太现实。用磁盘存都要 104857600000000 T 的空间,这基本上是不可实现的。
我给出一个算法,大家看看是否可行:
- 假定现有的质数表为 a1, a2, a3, ai
- 则产生一个子任务,计算 ai 到 ai^2 的质数;
- 第 2 步中产生大于 ai 的下一个质数 ai+1 后,可以产生一个新的子任务 ai^2a(i+1)^2,可以分配给另外一台机器;
举例子:
现在已经产生了 2,3,7,
其中一个子任务是计算 8-49 的质数,计算时,很快发现 11 也是质数,更新质数表,又产生一个新的子任务 49-121,完全可以在另一个计算机计算,后来有发现 13 也是,可以产生 121-169 的子任务,也提交到另外一个计算机,随着这个过程继续,不断产生更多的子任务,但是这些子任务都是可以独立运行的,不过要按顺序来,这样可以认为整个过程是两台或多台机器并行执行,是一台机器的 1/2。