筛法求素数
给定N，求解1 ~ N的所有素数。
一般做法为依次判断2 ~ N是否为偶数，其时间复杂度为O（N ^ 2）
筛法大体思路：
根据素数定义可知，若某个数能被其他素数整除，则其一定不为素数，因此可以依次筛掉1 ~ N中不是素数的数，剩下的即为所求。
public List<Integer> getPrime(int N){
boolean[] nonPrime = new boolean[N + 1];
List<Integer> ans = new ArrayList<>();
for(int i = 2; i <= N; i++) {
if(nonPrime[i]) {
continue;
}
ans.add(i);
for(int j = i; j * i <= N; j++) {
nonPrime[i * j] = true;
}
}
return ans;
}筛法求素数过程中，我们发现对于每个元素，最多被访问2次。因此其时间复杂度为O（N），由于使用了额外boolean[] nonPrime，因此额外空间复杂度亦为O（N）。
一个应用：孪生素数的求解
孪生素数定义：间隔为2的两个素数。（例如 （3， 5），（5， 7），（11， 13））
求解小于N的孪生素数的对数。
public int countTwicePrime(int N) {
boolean[] nonPrime = new boolean[N + 1];
int count = 0;
int prePrime = 2;
for(int i = 2; i <= N; i++) {
if(nonPrime[i]) {
continue;
}
if(i - prePrime == 2) {
count++;
}
prePrime = i;
for(int j = i; j * i <= N; j++) {
nonPrime[i * j] = true;
}
}
return count;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-09-14，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录