[关闭]
@yexiaoqi 2022-05-06T23:51:13.000000Z 字数 1377 阅读 274

找质数

刷题


题目:找出自然数 n 范围之内的质数


  1. /**
  2. * 埃氏筛与欧拉筛的比较
  3. * 找出自然数 n 范围之内的质数
  4. */
  5. public class 找质数 {
  6. private static final int MAX_LENGTH_CHECK = 100000001; // 亿
  7. private static final int MAX_LENGTH_PRIMELIST = 10000000;// 千万
  8. private static boolean[] check = new boolean[MAX_LENGTH_CHECK];
  9. private static int[] primeList = new int[MAX_LENGTH_PRIMELIST];
  10. /**
  11. * 埃氏筛:要得到自然数 n 以内的全部素数,必须把不大于 根号n 的所有素数的倍数剔除,剩下的就是素数。
  12. * 解法:先用2去筛,把2留下,2的倍数剔除;再用下一个质数3筛,把3留下,3的倍数剔除掉,不断重复……
  13. *
  14. * 时间复杂度:O(nloglogn)
  15. */
  16. private static void Eratosthenes(int num) {
  17. int count = 0;
  18. for (int i = 2; i <= num; i++) {
  19. // 当 i 不是要被剔除的数时,把 i 留下
  20. if (!check[i]) {
  21. primeList[count++] = i;
  22. }
  23. // 剔除 i 的倍数
  24. for (int j = i + i; j <= num; j += i) {
  25. check[j] = true; // 标记为剔除
  26. }
  27. }
  28. }
  29. /**
  30. * 欧拉筛:保证每个合数只会被它最小的质因数筛掉,时间复杂度降低到O(n)
  31. * 解法:每个数都去乘当前素数表里已有的数,当 i 是合数时且 i%primeList[j]==0 时,只能乘第一个素数
  32. */
  33. private static void Euler(int num) {
  34. int count = 0;
  35. for (int i = 2; i <= num; i++) {
  36. if (!check[i]) {
  37. primeList[count++] = i;
  38. }
  39. for (int j = 0; j < count; j++) {
  40. // 超过范围后跳出
  41. if (i * primeList[j] > num) {
  42. break;
  43. }
  44. check[i * primeList[j]] = true;
  45. // 保证每个合数只会被它最小的质因子筛掉
  46. if (i % primeList[j] == 0) {
  47. break;
  48. }
  49. }
  50. }
  51. }
  52. public static void main(String[] args) throws InterruptedException {
  53. int n = 100000000;
  54. long start,end;
  55. start = System.currentTimeMillis();
  56. Euler(n);
  57. end = System.currentTimeMillis();
  58. System.out.println("亿级别数量:欧拉筛,耗时:" + (end - start) + " ms");
  59. Arrays.fill(check, false);
  60. Arrays.fill(primeList, 0);
  61. start = System.currentTimeMillis();
  62. Eratosthenes(n);
  63. end = System.currentTimeMillis();
  64. System.out.println("亿级别数量:埃氏筛,耗时:" + (end - start) + " ms");
  65. }
  66. }

结果如下:

亿级别数量:欧拉筛,耗时:1109 ms
亿级别数量:埃氏筛,耗时:13135 ms
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注