埃拉托色尼筛法 - 实现返回一些非质数值?

2024-05-23

我用 Java 实现了埃拉托斯特尼筛法,通过伪代码:

public static void sieveofEratosthenes(int n) {
    boolean numArray[];

    numArray = new boolean[n];
    for(int i = 0; i < n; i++)
        numArray[i] = true;

    int a = 0;

    for(int i = 2; i < Math.sqrt((double)n); i++) {
        if(numArray[i])  {
            for(int j = (int)Math.pow(i, 2); j < n; a++) {
                numArray[j] = false;
                j += (a * i);
            }
        }
    }

    for(int i = 2; i < n; i++) {
        if(numArray[i])
            System.out.println(i);
    }
}

当 i 为 15 时,它给我的输出:

2
3
5
7
8
11
12
13
14

为什么其中一些值不正确?我相信我的错误在于如何定义和使用 bool 数组。谢谢!


        for(int j = (int)Math.pow(i, 2); j < n; a++) {
            numArray[j] = false;
            j += (a * i);
        }

应该读

        for(int j = (int)Math.pow(i, 2); j < n; j+=i) {
            numArray[j] = false;
        }
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

埃拉托色尼筛法 - 实现返回一些非质数值? 的相关文章

随机推荐