高效判定质数：埃拉托斯特尼筛法优化及内存节省
为了提升质数判断效率并降低内存消耗，本文采用埃拉托斯特尼筛法进行优化。传统方法逐个判断效率低下，而筛法则能显著提高速度。
埃拉托斯特尼筛法的步骤如下：
- 初始化一个布尔数组，所有元素初始值为
true，数组索引代表数字，true表示可能是质数。 - 从2开始遍历，对于每个未标记为合数的数字
i，将其所有倍数(2i,3i,4i……)标记为false，表示它们是合数。 - 遍历结束后，数组中仍为
true的索引对应的数字即为质数。
改进后的代码片段示例：
import java.util.Scanner;
public class PrimeChecker {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int limit = input.nextInt(); // 获取上限
boolean[] isPrime = new boolean[limit + 1];
java.util.Arrays.fill(isPrime, true); // 初始化数组
isPrime[0] = isPrime[1] = false; // 0和1不是质数
for (int p = 2; p * p <= limit; p++) {
if (isPrime[p]) {
for (int i = p * p; i <= limit; i += p)
isPrime[i] = false;
}
}
// 打印质数
for (int i = 2; i <= limit; i++) {
if (isPrime[i]) {
System.out.print(i + " ");
}
}
input.close();
}
}
通过埃拉托斯特尼筛法，我们可以有效减少判断次数，从而显著提升效率并优化内存使用。 请注意，代码片段仅供参考，实际应用中可能需要根据具体需求进行调整。
