素数,即为只能被1和它本身整除的正整数,其中1不为正整数,素数又称质数。
从2开始累加,同时对2进行标记素数,然后把2的其他倍数都去掉(或者标记为非素数),然后找到下一个没有标记的数,将其标记为素数,同时把它的其他倍数都去掉(或者标记为非素数)。如此反复,知道标记完所有的数,这样便找出了所有的素数。
LeetCode示例
计数质数
统计所有小于非负整数 n 的质数的数量。
示例:
输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
代码:
int countPrimes(int n) {
int size=0;
vector<bool> prime(n,false);
for(int i=2;i<n;i++)
{
if(prime[i])
continue;
size++;
/**
* 厄拉多塞筛选法
*/
for(int j=i+i;j<n;j+=i)
{
prime[j] = true;
}
}
return size;
}
【3】用6N±1法求素数。
任何一个自然数,总可以表示成为如下的形式之一:
6N,6N+1,6N+2,6N+3,6N+4,6N+5 (N=0,1,2,…)
显然,当N≥1时,6N,6N+2,6N+3,6N+4都不是素数,只有形如6N+1和6N+5的自然数有可能是素数。所以,除了2和3之外,所有的素数都可以表示成6N±1的形式(N为自然数)。
根据上述分析,我们可以构造另一面筛子,只对形如6 N±1的自然数进行筛选,这样就可以大大减少筛选的次数,从而进一步提高程序的运行效率和速度。
参考:
原文链接: https://www.cnblogs.com/xiao--ge/p/12993963.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/351922
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!