建设网站怎样做,免费网上销售平台,展厅策划设计公司,广告设计制作属于什么行业统计所有小于非负整数 n 的质数的数量。
示例 1#xff1a;
输入#xff1a;n 10 输出#xff1a;4 解释#xff1a;小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
解题思路
大于等于5的质数一定和6的倍数相邻。例如5和7#xff0c;11和13,17和19等等#xff1b…统计所有小于非负整数 n 的质数的数量。
示例 1
输入n 10 输出4 解释小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
解题思路
大于等于5的质数一定和6的倍数相邻。例如5和711和13,17和19等等
证明令x≥1将大于等于5的自然数表示如下
··· 6x-16x6x16x26x36x46x56(x16(x1)1 ···
可以看到不和6的倍数相邻的数为6x26x36x4由于2(3x1)3(2x1)2(3x2)所以它们一定不是素数再除去6x本身显然素数要出现只可能出现在6x的相邻两侧。因此在5到sqrt(n)中每6个数只判断2个时间复杂度O(sqrt(n)/3)。
代码
class Solution {public int countPrimes(int n) {int res0;for(int i2;in;i)resisPrimes(i);return res;}public int isPrimes(int n) {double nSqrt;if(n2||n3) return 1;if(n%6!1n%6!5) return 0;nSqrt Math.floor(Math.sqrt((double)n));for(int i5;inSqrt;i6)if(n%i0||n%(i2)0) return 0;return 1;}
}
