如何用埃拉托斯特尼筛法优化判定质数并减少内存占用？-java教程-PHP中文网

如何用埃拉托斯特尼筛法优化判定质数并减少内存占用？

花韻仙語

发布： 2025-02-20 21:36:10

原创

844人浏览过

如何用埃拉托斯特尼筛法优化判定质数并减少内存占用？

高效判定质数：埃拉托斯特尼筛法优化及内存节省

为了提升质数判断效率并降低内存消耗，本文采用埃拉托斯特尼筛法进行优化。传统方法逐个判断效率低下，而筛法则能显著提高速度。

埃拉托斯特尼筛法的步骤如下：

卡拉OK视频制作

卡拉OK视频制作，在几分钟内制作出你的卡拉OK视频

178

查看详情

初始化一个布尔数组，所有元素初始值为true，数组索引代表数字，true表示可能是质数。
从2开始遍历，对于每个未标记为合数的数字i，将其所有倍数(2i, 3i, 4i……)标记为false，表示它们是合数。
遍历结束后，数组中仍为true的索引对应的数字即为质数。

改进后的代码片段示例：

<code class="java">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();
    }
}</code>

登录后复制

通过埃拉托斯特尼筛法，我们可以有效减少判断次数，从而显著提升效率并优化内存使用。请注意，代码片段仅供参考，实际应用中可能需要根据具体需求进行调整。

以上就是如何用埃拉托斯特尼筛法优化判定质数并减少内存占用？的详细内容，更多请关注php中文网其它相关文章！