用java写一个欧拉Euler筛并解释代码含义
时间: 2024-05-01 20:16:20 浏览: 17
欧拉筛是一种高效的素数筛法,它可以在线性时间复杂度内计算出一定范围内的所有素数。
以下是用Java实现欧拉筛的代码:
```java
public static int[] eulerSieve(int n) {
int[] primes = new int[n + 1];
boolean[] isPrime = new boolean[n + 1];
int cnt = 0;
Arrays.fill(isPrime, true);
for (int i = 2; i <= n; i++) {
if (isPrime[i]) {
primes[cnt++] = i;
}
for (int j = 0; j < cnt && i * primes[j] <= n; j++) {
isPrime[i * primes[j]] = false;
if (i % primes[j] == 0) {
break;
}
}
}
return Arrays.copyOf(primes, cnt);
}
```
代码含义:
1. 定义一个长度为n+1的整数数组primes,用于存储筛出的素数。
2. 定义一个长度为n+1的布尔型数组isPrime,用于标记每个数是否为素数。
3. 定义一个计数器cnt,用于记录筛出的素数个数。
4. 使用Arrays.fill方法将isPrime数组全部初始化为true,表示初始时所有数都是素数。
5. 从2开始遍历到n,如果isPrime[i]为true,说明i是一个素数,将它加入primes数组中,并将cnt加1。
6. 遍历primes数组中的每个素数,将i乘以素数得到的数标记为非素数,即将isPrime[i * primes[j]]设为false。
7. 如果i能够整除primes[j],说明i的下一个素数是primes[j],不需要再继续遍历primes数组中的其他素数,直接break跳出循环。
最后,将primes数组的前cnt个元素复制到一个新数组中,即可得到所有小于等于n的素数。