Eratosthenes筛-实现返回一些非素值? [英] Sieve of Eratosthenes - Implementation returning some non-prime values?

问题描述

我用伪代码在Java中实现了Eratosthenes筛子:

I implemented the Sieve of Eratosthenes in Java, from pseudocode:

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);
    }
}

当我15岁时，它给我的输出:

The output it gives me, when i is 15:

2
3
5
7
8
11
12
13
14

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

Why are some of these values incorrect? I believe my error is in how I define and use the bool array. Thanks!

推荐答案

        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;
        }

这篇关于Eratosthenes筛-实现返回一些非素值?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！