|
|
大家好啊, 我们这个质数系列总算推进到了千亿级别. 这次我们准备将算法和代码分成两篇文章讲. 这篇文章将对算法进行详解. 下篇文章将着重介绍代码.
在求 200 亿和 100 亿以前的所有质数中, 我用的是埃氏筛算法, 而这次求 1000 亿, 我准备用一下欧拉筛.
欧拉筛的原理是这样的,
我们先列出 1\sim n 的所有数字.
\begin{matrix}2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17\end{matrix}
然后从前往后读取, 第一个数 2 没有被划去, 则认为其为质数,
对于质数, 那么就要遍历该质数之前的所有质数(包括他本身), 依次划掉之前的所有质数和该质数的乘积.
那么, 划掉 2\times2=4
\begin{matrix}2&3&\cancel4&5&6&7&8&9&10&11&12&13&14&15&16&17\end{matrix}
继续往后读取, 下一个没有被划去的数字是 3 , 认为其是质数, 所以遍历之前的所有质数 2,3 , 划去 3 和这些质数的乘积, 3\times2=6,3\times3=9
\begin{matrix}2&3&\cancel4&5&\cancel6&7&8&\cancel9&10&11&12&13&14&15&16&17\end{matrix}
我们继续往后读取, 下一个数字是 4 , 因为他被划掉了, 所以我们认为他是合数. 对于合数, 处理的步骤就要麻烦一点.
我们划去 2\times4=8
\begin{matrix}2&3&\cancel4&5&\cancel6&7&\cancel8&\cancel9&10&11&12&13&14&15&16&17\end{matrix}
下一个本应该和 4 相乘的数字是 3 , 但这时候, 注意到 \text{mod(4,2)}=0 , 即 2 整除 4 . 所以停止对于 4 的操作, 我们读取下一个数.
也就是说, 对于合数我们要这样处理:
划去其和第一个质数 2 的乘积, 检查其是否能被 2 整除, 如果能, 开始读取下一个数, 如果不能, 划去其和下一个质数 3 的乘积, 检查是否能被 3 整除, 如果能, 开始读取下一个数, 如果不能, 划去其和下一个质数的乘积, 以此类推.
下一个我们读取 5 , 没有被划去, 我们认为是质数, 因此划去
5\times2=10,5\times3=15,(5\times5=25)
\begin{matrix}2&3&\cancel4&5&\cancel6&7&\cancel8&\cancel9&\cancel{10}&11&12&13&14&\cancel{15}&16&17\end{matrix}
下一个数字是 6 , 划去 12 ,
\begin{matrix}2&3&\cancel4&5&\cancel6&7&\cancel8&\cancel9&\cancel{10}&11&\cancel{12}&13&14&\cancel{15}&16&17\end{matrix}
6 被 2 整除, 开始读取下一个数 7
划去 14,(21),(35),(49) 括号代表超出范围, 不做处理.
\begin{matrix}2&3&\cancel4&5&\cancel6&7&\cancel8&\cancel9&\cancel{10}&11&\cancel{12}&13&\cancel{14}&\cancel{15}&16&17\end{matrix}
下一个数字是 8 , 被划去, 所以为合数. 所以划掉 16
\begin{matrix}2&3&\cancel4&5&\cancel6&7&\cancel8&\cancel9&\cancel{10}&11&\cancel{12}&13&\cancel{14}&\cancel{15}&\cancel{16}&17\end{matrix}
8 被 2 整除, 读取下一个数.
9\times2=18>17 , 停止读取.
重新从前往后读取出所有质数,
2,3,5,7,11,13,17
<hr/>那么, 我们现在要解决的问题就是,
1.如何证明我们划去了所有合数,
2.如何证明每个质数都仅被其最小质因子划去(解决了埃氏筛多次划去同一个数的问题)
实际上, 若一个合数仅能分解为两个质数相乘, 那么我们一定能把他划去, 因为我们在读取到一个新质数的时候遍历了之前所有质数和他的乘积.
若一个合数能分解为多个质数相乘. 那么其一定能表示为一个质数和一个合数相乘, 假设该数 A=pc
p 表示其最小质因子, c 表示一个大于 p 的合数. 那么当我们读取到 c 的时候, 我们划去了 2c , 如果 A 不能被 2 整除, 我们还会划去 3c , 总有一个时刻我们会划去 pc , 这时候, 因为 A 被 p 整除, 停止.
所以, 对于任意能分解为多个质数相乘的合数, 都一定能被我们划去.
而一个合数要么能分解为两个质数相乘, 要么能分解为多个质数相乘. 所以一切合数都能被我们划去.
而对于能分解为两个质数相乘的合数来说, 其仅可能被划去一次,
对于能分解为多个质数相乘的合数来说, 当其被 p 整除的时候, 就停止, 所以不会划掉 2pc,3pc 这些质数, 所以每个合数都只会被划去一次.
<hr/>提前透露一些信息, 1000 亿以前一共 4118054813 ( 41 亿个质数).
<hr/><hr/>文章封面
蛍(Lumine) #5 |
|
发表于 2023-1-9 10:49:58