使用埃拉托斯特尼筛选法获取质数的 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
广告