一、题目描述
======
统计所有小于非负整数
n
的质数的数量。示例 1:
输入:n = 10 输出:4 解释:小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。 示例 2:
输入:n = 0 输出:0 示例 3:
输入:n = 1 输出:0
提示:
0 <= n <= 5 * 106
二、思路分析
======
public int countPrimes(int n) {
int total = 0;
for (int i = 2; i < n; i++) {
int j=2;
for (j = 2; j < i; j++) {
if (i % j == 0) {
break;
}
}
if (j == i) {
total++;
}
}
return total;
}
三、升级之路+AC代码
===========
减少暴力次数
6\=6∗66=\sqrt{6} * \sqrt{6}6\=6∗6
public int countPrimes(int n) {
int total = 0;
for (int i = 2; i < n; i++) {
boolean flag = false;
for (int j = 2; j*j <= i; j++) {
if (i % j == 0) {
flag=true;
break;
}
}
if (!flag) {
total++;
}
}
return total;
}
埃筛法
1*3;2*3;3*3......;n*3
这些数据都是合数,在循环检测中就不需要在判断他们是不是质数了。这样就大大的减少了我们排查的次数4,6,8,10,12,14
都将被标记为合数。因为题目考核的是n以下的数字,所以这里16不需要考虑public int countPrimes2(int n) {
int total = 0;
//构造同等长度的状态位数组, 默认false表示质数
boolean[] primes = new boolean[n];
for (int i = 2; i < n; i++) {
if (!primes[i]) {
total++;
for (int j = 2 * i; j < n; j += i) {
primes[j] = true;
}
}
}
return total;
}
埃筛法2
2*5
的2质数渲染成合数了。但是10会再次被5*2
渲染合数。这个道理和上面暴力法升级中是同样的问题。为了避免类似10=2*5
,乘数位置交换的问题,我们可以在延伸的时候从质数的平方开始,因为质数的之前肯定会被之前的质数渲染public int countPrimes3(int n) {
int total = 0;
//构造同等长度的状态位数组, 默认false表示质数
boolean[] primes = new boolean[n];
for (int i = 2; i < n; i++) {
if (!primes[i]) {
total++;
if ((long)i * i >= n) {
continue;
}
for (int j = i * i; j < n; j += i) {
//System.out.println("index="+j+"i="+i);
primes[j] = true;
}
}
}
return total;
}
四、总结
====
我正在参与2023腾讯技术创作特训营第三期有奖征文,组队打卡瓜分大奖!
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。