请用java写一个两次筛法
时间: 2023-01-28 19:15:34 浏览: 77
好的,这是用 Java 实现两次筛法的代码示例:
```
public class TwoPassSieve {
public static void main(String[] args) {
// 设置筛选的上界
int n = 100;
// 第一次筛法,求出小于等于根号 n 的所有质数
boolean[] isPrime = new boolean[n + 1];
Arrays.fill(isPrime, true);
int sqrt = (int) Math.sqrt(n);
for (int i = 2; i <= sqrt; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
// 第二次筛法,求出大于根号 n 的所有质数
List<Integer> primes = new ArrayList<>();
for (int i = sqrt + 1; i <= n; i++) {
if (isPrime[i]) {
primes.add(i);
}
}
for (int i = 0; i < primes.size(); i++) {
int p = primes.get(i);
for (int j = i + 1; j < primes.size(); j++) {
int q = primes.get(j);
if (p * q > n) {
break;
}
isPrime[p * q] = false;
}
}
// 输出结果
for (int i = 2; i <= n; i++) {
if (isPrime[i]) {
System.out.println(i);
}
}
}
}
```
算法的思路是:
1. 先使用线性筛法求出小于等于根号 n 的所有质数;
2. 将剩下的数字按照质数的顺序存储到一个列表中;
3. 再对这个列表中的每个质数进行两两相乘,如果结果超过了 n,则退出循环;
4. 最后输出所有的质数。
这个算法的时间复杂度是 O(n log log