当前位置: 代码迷 >> 综合 >> JAVA算法:统计素数的数量
  详细解决方案

JAVA算法:统计素数的数量

热度:17   发布时间:2024-01-15 19:19:00.0

JAVA算法:统计素数的数量

统计所有小于非负整数 n 的质数的数量。

示例:

输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。


算法设计

用数组flag标记非素数,每当出现一个flag[i]为false,计数器count加一。
关于素数有三点:

  1. 大于3的素数一定是奇数,如3,5,7;
  2. 奇数中的非素数也一定是奇数的乘积。
  3. 对于一个很大的数n,它的两个因数i和j中一定有一个小于n的开方,所以我们让i <= Math.sqrt(n),j >= n,这样可以避免重复讨论一些情况。

首先,我们用i从3到Math.sqrt(n)进行标记。
其次,根据上述的第2、3两点,通过乘积i*j对应index的方法对在flag中对合数为index的值赋值true,j+=2,外层一样,i+=2,因为大于3的数中只有奇数有可能是质数,而这些质数i可以通过j的循环标记所有i作为因数的合数。
标记完所有的合数之后,再用Math.sqrt(n)到n之间的遍历,count所有未被标记true的质数。

public int countPrimes(int n) {boolean[] mark = new boolean[n];if (n <= 2) return 0;int i = 3, count = 1; //i from 3, so there is o