@yexiaoqi
2022-05-07T07:51:13.000000Z
字数 1377
阅读 364
刷题
题目:找出自然数 n 范围之内的质数
/**
* 埃氏筛与欧拉筛的比较
* 找出自然数 n 范围之内的质数
*/
public class 找质数 {
private static final int MAX_LENGTH_CHECK = 100000001; // 亿
private static final int MAX_LENGTH_PRIMELIST = 10000000;// 千万
private static boolean[] check = new boolean[MAX_LENGTH_CHECK];
private static int[] primeList = new int[MAX_LENGTH_PRIMELIST];
/**
* 埃氏筛:要得到自然数 n 以内的全部素数,必须把不大于 根号n 的所有素数的倍数剔除,剩下的就是素数。
* 解法:先用2去筛,把2留下,2的倍数剔除;再用下一个质数3筛,把3留下,3的倍数剔除掉,不断重复……
*
* 时间复杂度:O(nloglogn)
*/
private static void Eratosthenes(int num) {
int count = 0;
for (int i = 2; i <= num; i++) {
// 当 i 不是要被剔除的数时,把 i 留下
if (!check[i]) {
primeList[count++] = i;
}
// 剔除 i 的倍数
for (int j = i + i; j <= num; j += i) {
check[j] = true; // 标记为剔除
}
}
}
/**
* 欧拉筛:保证每个合数只会被它最小的质因数筛掉,时间复杂度降低到O(n)
* 解法:每个数都去乘当前素数表里已有的数,当 i 是合数时且 i%primeList[j]==0 时,只能乘第一个素数
*/
private static void Euler(int num) {
int count = 0;
for (int i = 2; i <= num; i++) {
if (!check[i]) {
primeList[count++] = i;
}
for (int j = 0; j < count; j++) {
// 超过范围后跳出
if (i * primeList[j] > num) {
break;
}
check[i * primeList[j]] = true;
// 保证每个合数只会被它最小的质因子筛掉
if (i % primeList[j] == 0) {
break;
}
}
}
}
public static void main(String[] args) throws InterruptedException {
int n = 100000000;
long start,end;
start = System.currentTimeMillis();
Euler(n);
end = System.currentTimeMillis();
System.out.println("亿级别数量:欧拉筛,耗时:" + (end - start) + " ms");
Arrays.fill(check, false);
Arrays.fill(primeList, 0);
start = System.currentTimeMillis();
Eratosthenes(n);
end = System.currentTimeMillis();
System.out.println("亿级别数量:埃氏筛,耗时:" + (end - start) + " ms");
}
}
结果如下:
亿级别数量:欧拉筛,耗时:1109 ms
亿级别数量:埃氏筛,耗时:13135 ms