质数查找器错误-将非质数显示为质数

Question

我一直在解决euler项目中的问题，而不是使用bruteforce，我想用一个高质量的解决方案来完成这些问题。我构建它是为了找到质数，并一直在测试它的值。当我寻找第12个素数时，它告诉我它是35 (显然不是)。

它应该将35标识为非质数，因为所有之前的素数都被添加到一个列表中，但这里出现了一些问题。有什么想法吗？

public static void main (String[] args) {
    int nthTerm = 12;
    int count = 3;
    int nPrime = 3;
    ArrayList<Integer> primeList = new ArrayList<>();
    primeList.add(3);
    int upperBoundary;
    ArrayList<Integer> checkList = new ArrayList<>();
    int check;
    boolean isPrime;

    while (count < nthTerm) {
        isPrime = false;
        nPrime += 2;

        for (int i = 0; i < primeList.size(); i++){
            upperBoundary = (int) Math.floor(Math.sqrt(nPrime));
            if (primeList.get(i) <= upperBoundary){
                checkList.add(primeList.get(i));
            }
        }

        for (int j = 0; j < checkList.size(); j++){
            check = checkList.get(j);
            if (nPrime % check == 0){
                isPrime = false;
                break;
            } else {
                isPrime = true;
                primeList.add(nPrime);
            }
        }

        if (isPrime == true) {
            count++;
        }

    }
    System.out.println("Prime number " + count + ": " + nPrime);

}

}

Answer 1

首先，您不需要在第一个for循环中重新计算upperBoundary。该值不会在该循环的每次迭代中更改，因此只需在while循环中计算它即可。

其次，对于较低的nPrime值，您不会向checkList中添加任何内容。这是问题的根源。值5永远不会添加到该列表中，因此25和35都被标识为质数。

最后，您应该通过在调试器中运行代码来调试代码，或者至少在中间步骤中打印出一些值。查看被您的算法标识为质数的所有值以及checkList变量中的所有值，应该会引导您找到解决方案。

(此外，在这里发布问题时，解释您的方法也会有所帮助。如果对代码试图做的事情有一个解释，那么就更容易理解代码的错误所在。)

Answer 2

试试这个：

public static void main(String[] args) {
    int nthTerm = 12;
    int nPrime = 3;
    List<Integer> primeList = new ArrayList<>();
    primeList.add(2);
    primeList.add(3);

    while (primeList.size() < nthTerm) {
        nPrime += 2;

        boolean isPrime = true;
        for (int primeIndex = 1; primeIndex < primeList.size(); primeIndex++) {
            int prime = primeList.get(primeIndex);
            if (nPrime % prime == 0) {
                isPrime = false;
                break;
            }
        }
        if (isPrime) {
            primeList.add(nPrime);
            System.out.println("Prime number " + primeList.size() + ": " + nPrime);
        }

    }

    System.out.println("Prime number " + nthTerm + ": " + nPrime);

}

你代码的问题是：

，，

• ，你在列表中添加了非素数，例如25。仅仅因为25%3 == 1(如果不是质数的倍数，则添加for -没有检查全部)
• checklist从未清除-它可以包含多个元素，如: 3，3，3，3，5，...