相关资料以及注意事项:
- 我的LeetCode解题集GitHub地址
- 欢迎私信或者留言交流!
算法介绍
要得到自然数n以内的全部素数,必须把不大于根号n的所有素数的倍数剔除,剩下的就是素数。
算法过程
for (int i = 0; i < n; i++) {
arr[i] = true;
}
arr[0] = false;
int count = 0;
int limit = (int) Math.sqrt(n);
// 埃拉托斯特尼筛法
for (int i = 2; i <= limit; i++) {
if (arr[i - 1]) {
// 把能被整除的数字标识出来
for (int j = i * i; j < n; j += i) {
arr[j - 1] = false;
}
}
}
- 首先建立一个布尔表arr,全部标记为True,然后开始进行剔除。
- 只需要计算2到n的开方之内的素数即可。
- 假如arr标记的为素数,就开始进行剔除。
- j的起始点为 i * i,因为
i*1 ——> i * (i -1)
在之前的(i-1)*i
循环里已经剔除过了。 - 开始剔除,因为对应的数字是大于等于1的正整数,所以标记arr[j-1]即可。同理之前判断的a[i-1]。
- 循环完毕后,剩下标记为True的即为素数。
总结心得
妙啊,真是妙啊!
网友评论