java如何查质数个数
时间: 2023-10-18 12:16:43 浏览: 47
以下是一种简单的方法来查找小于或等于给定数字的质数的个数:
```
public static int countPrimes(int n) {
if (n <= 2) {
return 0;
}
boolean[] isPrime = new boolean[n];
for (int i = 2; i < n; i++) {
isPrime[i] = true;
}
for (int i = 2; i * i < n; i++) {
if (!isPrime[i]) {
continue;
}
for (int j = i * i; j < n; j += i) {
isPrime[j] = false;
}
}
int count = 0;
for (int i = 2; i < n; i++) {
if (isPrime[i]) {
count++;
}
}
return count;
}
```
该方法使用了一个布尔数组isPrime,其中isPrime[i]表示数字i是否为质数。首先,将数组中所有元素初始化为true。然后,从2开始遍历数组,如果发现isPrime[i]为true,则说明i是质数,将i的所有倍数标记为false。最后,统计isPrime数组中为true的元素的个数,即为小于或等于n的质数的个数。
该方法的时间复杂度为O(nloglogn),空间复杂度为O(n)。