holyya.com
2025-09-10 20:50:11 Wednesday
登录
文章检索 我的文章 写文章
我最近在学习Java编程语言
2023-06-11 02:33:04 深夜i     --     --

我最近在学习Java编程语言,其中实现求素数是一个重要的算法。我想分享一下我编写的Java求素数的代码。

关键词一:算法

首先,我先了解了求素数的算法。最常用的算法是试除法,即将一个数n分别除以2到n-1之间的所有数,如果都不能整除,则n为素数。这个算法虽然直观,但是时间复杂度较高。

关键词二:优化

为了优化这个算法,我采用了一个更高效的算法——埃氏筛法。这个算法的思想是先将2到n-1的数写出来,然后从2开始,将其所有的倍数全部去掉,最后留下的数即为素数。这个算法的时间复杂度为O(nloglogn),较试除法更为高效。

关键词三:代码实现

现在,我将我的埃氏筛法的Java代码分享给大家,希望能够帮助到正在学习Java编程语言的同学们。


public static boolean[] sieveOfEratosthenes(int n) {

  boolean[] isPrime = new boolean[n + 1];

  Arrays.fill(isPrime, true);

  isPrime[0] = false;

  isPrime[1] = false;

  for (int i = 2; i * i <= n; i++) {

    if (isPrime[i]) {

      for (int j = i * i; j <= n; j += i) {

        isPrime[j] = false;

      }

    }

  }

  return isPrime;

}

这个代码使用了一个boolean数组来表示是否为素数,数组下标即为待测试的数字,数组元素值表示该数字是否为素数。首先将2到n-1的数全部标记为素数,再从2开始,如果该数字为素数,则将其所有倍数标记为非素数。最后遍历数组,返回结果即可。

标题:Java求素数,用埃氏筛法更高效

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复