BitTigerio 2018-04-22
问题:求 0-N 内素数的个数。
预备知识
public void countPrime_1(int n) { // 之所以数组范围设置为 n+1,是因为数组从下标为 1 开始计数,n表示最后一个数 // 数组初始值为false,因为我们假设false代表是素数,true代表不是素数 boolean[] b = new boolean[n + 1]; // 2 - n 每个数逐一判断 for (int i = 2; i <= n; i++) { // 【2,√i】 for (int j = 2; j * j <= i; j++) { if (i % j == 0) { // 在判断 i 是否为素数的过程中,遍历 2 - √i // 一旦发现在【2,√i】中,有数整除了,将数组b中下标为i的设置为true, // 代表不是素数,并且中断内层for循环,因为已经判断出i不是素数了,没有必要 // 继续循环判断下去。 直接判断第i+1个数 b[i] = true; break; } } } /** * 此部分内容在接下来将不写 */ int count = 0; // 下标从2开始,是因为 1 不是素数也不是合数,没有必要判断 for (int i = 2; i <= n; i++) { // 当为false时,代表素数 if (b[i] == false) { count++; } } }
注意:在第10行中的for循环内,使用的是 j * j <= i ,而不是 j <= sqrt(i)。原因:第一:sqrt是用来处理浮点数的,而浮点数的计算速度远远慢于integer。第二,函数调用也会造成时间的浪费。第三:浮点数的存储误差可能引出致命错误,如 sqrt(9) 可能等于 2.9999999 ,那么 int(sqrt(9)) 就等于2 而不是3。
筛选法:在一张纸上写上 1-n 全部整数,然后逐个判断是否为素数,找出一个非素数,就把它挖掉,最后剩下的就是素数。
具体做法如下:
public void countPrime_2(int n) { boolean[] b = new boolean[n + 1]; for (int p = 2; p * p <= n; p++) { // 假设当 p 为2时,也就是判断在数组 b 中下标为 2 的值是不是false,即 数字2 是不是素数 // 如果是素数,就将 2 的倍数 4 6 8 10 等等全部标记为 非素数,即b[2] b[4] b[6] 的值为true if (b[p] == false) { /** * 当 p 为 3 时,j = 3 * 3 = 9 。哎??? 怎么直接将 9 标记为 非素数了 ??? * 不应该是将 6 先标记为 非素数吗? 直接标记 9 了,那 6 怎么办 ??? * 因为: 6 也是 素数2的倍数,在计算素数 2 的时候就已经将6除去了 * 所以直接从 p * p 开始计算,相当于又优化了 * j = j + p 代表跳到 p 的下一个倍数 */ for (int j = p * p; j <= n; j = j + p) { if (b[j] == false) { b[j] = true; } } } } }
对于一个数p,会依次去除p*p , p*(p+1) , p*(p+2) .... p*(p+k)【p*(p+k)<=n】
前面不是说要去除 p 的所有倍数的吗?那 p*2 ,p*3, p*4 ... p*(p-1)怎么不去除呢?
他们已经被去除了。因为当前我们要消去 p 的倍数,那么,之前一定去除了 2 3 4 ...p-3 , p-2 ,p-1 的这些数 的倍数,举个例子:之前一定去除了 2*p 3*p 4*p (p-1)*p。所以 , 当想去除p的倍数时,如果我们还是去除 p*2 p*3 p*4 p*(p-1) 那么岂不是与 我们去除2的倍数时 会去除 2*p 、去除3的倍数时 会去除 3*p、去除4的倍数时 会去除 4*p 重复了 ???