Java程序使用Eratosthenes算法的筛子获得质数

要查找不超过给定限制的所有质数，请使用Eratosthenes筛分算法。首先我们设置了要检查的值-

int val = 30;

现在，我们获取了一个布尔数组，其长度比val长一倍-

boolean[] isprime = new boolean[val + 1];

循环遍历val并将数字设置为TRUE。另外，将0和1设置为false，因为这两个数字都不是素数-

isprime[0] = false;
isprime[1] = false;

以下示例显示了使用Eratosthenes算法的Sieve算法获取质数的其余步骤-

示例

public class Demo {
   public static void main(String[] args) {
      //设置要检查的值
      int val = 30;
      boolean[] isprime = new boolean[val + 1];
      for (int i = 0; i <= val; i++)
      isprime[i] = true;
      //0和1不是素数
      isprime[0] = false;
      isprime[1] = false;
      int n = (int) Math.ceil(Math.sqrt(val));
      for (int i = 0; i <= n; i++) {
         if (isprime[i])
         for (int j = 2 * i; j <= val; j = j + i)
         //不是素数
         isprime[j] = false;
      }
      int myPrime;
      for (myPrime = val; !isprime[myPrime]; myPrime--) ; // empty loop body
      System.out.println("Largest prime less than or equal to " + val + " = " + myPrime);
   }
}

输出结果

Largest prime less than or equal to 30 = 29