22998的求质数的算法怎么算
来源：蜘蛛抓取(WebSpider)
时间：2017-12-11 15:22
标签：
怎么算质数
//判断是否是一个素数
//0,1负数都是非素数
//计算枚举上界，为防止double值带来的精度损失所以采用根号值取整后再加1，即宁愿多枚举一个也不愿少枚举一个数
//依次枚举这些数能否整除x，若能则必不是素数
//判断是否是一个素数 Mark 标记数组 index 素数个数
//标记该素数的倍数为非素数
这种方法比较好理解初始时，假设全部嘟是素数当找到一个素数时，显然这个素数乘上另外一个数之后都是合数
把这些合数都筛掉即算法名字的由来。但仔细分析能发现這种方法会造成重复筛除合数，影响效率
比如30，在i=2的时候k=2*15筛了一次；在i=5，k=5*6 的时候又筛了一次所以，也就有了快速线性筛法
//判断是否是一个素数 Mark 标记数组 index 素数个数
//如果未标记则得到一个素数
//标记目前得到的素数的i倍为非素数
利用了每个合数必有一个最小素因子。每个匼数仅被它的最小素因子筛去正好一次所以为线性时间。
代码中体现在：
if(i%prime[j]==0)break;
prime数组 中的素数是递增的,当 i 能整除 prime[j]那么 i*prime[j+1] 这个合数肯定被 prime[j] 乘以某個数筛掉。
因为i中含有prime[j], prime[j] 比 prime[j+1] 小接下去的素数同理。所以不用筛下去了
在满足i%prme[j]==0这个条件之前以及第一次满足改条件时,pr[j]必定是pr[j]*i的最小因子。
//判断是否是一个素数
//0,1负数都是非素数
//计算枚举上界，为防止double值带来的精度损失所以采用根号值取整后再加1，即宁愿多枚举一个也不愿少枚举一个数
//依次枚举这些数能否整除x，若能则必不是素数
//判断是否是一个素数 Mark 标记数组 index 素数个数
//标记该素数的倍数为非素数
这种方法比较好理解初始时，假设全部嘟是素数当找到一个素数时，显然这个素数乘上另外一个数之后都是合数
把这些合数都筛掉即算法名字的由来。但仔细分析能发现這种方法会造成重复筛除合数，影响效率
比如30，在i=2的时候k=2*15筛了一次；在i=5，k=5*6 的时候又筛了一次所以，也就有了快速线性筛法
//判断是否是一个素数 Mark 标记数组 index 素数个数
//如果未标记则得到一个素数
//标记目前得到的素数的i倍为非素数
利用了每个合数必有一个最小素因子。每个匼数仅被它的最小素因子筛去正好一次所以为线性时间。
代码中体现在：
if(i%prime[j]==0)break;
prime数组 中的素数是递增的,当 i 能整除 prime[j]那么 i*prime[j+1] 这个合数肯定被 prime[j] 乘以某個数筛掉。
因为i中含有prime[j], prime[j] 比 prime[j+1] 小接下去的素数同理。所以不用筛下去了
在满足i%prme[j]==0这个条件之前以及第一次满足改条件时,pr[j]必定是pr[j]*i的最小因子。
