使用埃拉托斯特尼筛选法获取质数的 Java 程序


要查找任何给定限制内的所有质数,使用埃拉托斯特尼筛选法。首先,我们设置要检查的值 -

int val = 30;

现在,我们取一个布尔数组,长度比 val 长 1 -

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

遍历 val 并将数字设置为 TRUE。同时,将 0 和 1 设置为 false,因为这两个数字都不是质数 -

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

以下是显示使用埃拉托斯特尼筛选法获取质数的其余步骤的示例 -

示例

 动态演示

public class Demo {
   public static void main(String[] args) {
      // set a value to check
      int val = 30;
      boolean[] isprime = new boolean[val + 1];
      for (int i = 0; i <= val; i++)
      isprime[i] = true;
      // 0 and 1 is not prime
      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)
         // not prime
         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

更新于: 30-Jul-2019

307 次观看

开启您的 职业生涯

完成课程后获得认证

开始
广告