新沂市建设局网站,中国建设银行人事网站,可以做视频剪辑兼职的网站,石家庄官网设计及搭建啊#xff0c;哈喽#xff0c;小伙伴们大家好。我是#张亿#xff0c;今天呐#xff0c;学的是理论知识.质数打表
为什么需要质数打表
我们已经学习了如何判断一个数是不是质数了#xff0c;但是还不够。假设要判断很多很多个数是不是质数的时候#xff0c;之前的学习的…啊哈喽小伙伴们大家好。我是#张亿今天呐学的是理论知识.质数打表
为什么需要质数打表
我们已经学习了如何判断一个数是不是质数了但是还不够。假设要判断很多很多个数是不是质数的时候之前的学习的方法效率不够高。因为如果 n 是质数需要从 2 枚举到 sqrt(n) 如果题目里面要你几百几千个数逐一判断是否是质数则很可能会超时。
所谓 质数打表是指先通过一段比较高效的代码完成了前期运算把每一个数是不是质数的信息 表格化 在程序的其它位置如果需要判断一个数是不是质数只需要去这个预先计算好的表格里面查一下就可以了。
质数打表的算法思路
我们只需要把合数找到那么自然就能找到质数了。而找合数的思路则是从小到大去找质数每找到一个新的质数则去把这个质数的倍数标记出来这些倍数就是合数而那些自始至终没有被标记过的数就是质数。例如当我们指导 13 是质数的时候我们就把 26,39,52,65... 等一系列的合数标记出来。课程E.倍数 的这条题就是演练这个算法思想的。
下面是质数打表的代码
bool flag[1000001];
void prepare_prime() //质数打表的函数
{int i,j;for(i2;i1000000;i){if(!flag[i]) //表示 i是一个质数{for(j2;i*j1000000;j) //对 j 的倍数不包含自己全部设置标记表示这些数是合数 flag[i*j] true }}
}Copy
执行了上面的 prepare_prime( ) 函数就产生了 1000000 以内的质数表了。当 flag[i] 为true表示 i 是合数flag[i] 为 false 则表示 i 是质数。 1 是特殊的1 既不是质数又不是合数单独判断。
常见错误
本来题目要你找出 n 以内的素数但是你打表的时候的第一层循环只循环到 sqrt(n) 这是错误的这会漏掉了很多 比 sqrt(n) 大的质数。
