Eratosthenes筛子（使用LINKEDLIST）

Question

我试图弄清楚我如何操纵列表，以便找到用户提供的所有素数，我有一个列表步骤，我试图遵循哪些是

创建并填充可能的素数列表

基本上是一个数组列表，其中包含所有数字，直到提供的数字，我已经完成了该部分

为素数创建列表

我有那部分下来

虽然仍然有可能的数字

也就是说，虽然可能的素数列表不是空的。

将可能列表中的第一个数字添加到素数列表中

把那部分也放下了

从可能的素数列表中删除它及其倍数

这就是我开始发呆的地方，我以为我有那个部分，但我得到了一个错误，我不知道为什么。

打印素数

打印素数列表，基本上只是System.out.println（素数）;

这是我目前的代码

import java.util.ArrayList;

import java.util.LinkedList;

import java.util.List;

import java.util.Scanner;

public class Sieve {

public static void main(String[] args) {

    int maxNum;

    String howItsGoing, greatDetail;

    Scanner scnr = new Scanner(System.in);

    Scanner scnr2 = new Scanner(System.in);

    // get upper limit

    System.out.print("What's the biggest number I should check? ");

    maxNum = scnr.nextInt();

    // check for verbose mode

    System.out.print("Shall I tell you how it's going? ");

    howItsGoing = scnr2.nextLine().toUpperCase();

    System.out.print("Shall I tell you in great detail? ");

    greatDetail = scnr2.nextLine().toUpperCase();

    // create and fill list of possible primes

    List<Integer> nums = new LinkedList<>();

    for (int i = 2; i <= maxNum; i++) {

        nums.add(i);         

    }

    // create list for the primes

    List<Integer> primes = new ArrayList<>();

    // while there are still possible numbers

    // add the first number from the list of possibles to the list of primes

    for(int i=2; i<=maxNum; i++) {

        if(2 % i == 0) {

            nums.remove((Integer) i);

            primes.add((Integer) i);

        }

    }

        // remove it and its multiples from the list of possible primes

    // print the prime numbers

    System.out.println("Primes up to " + maxNum);

    System.out.println(nums);

    System.out.println(primes);

}

}

忽略 howItsGoing 字符串和 greatDetail，我稍后会添加它们。

我如何让这个程序正常工作，其他每个问题都有布尔数组中的解决方案，这不是我想要的。有什么想法吗？

输出

What's the biggest number I should check? 9

Shall I tell you how it's going? n

Shall I tell you in great detail? n

Primes up to 9

[3, 4, 5, 6, 7, 8, 9]

[2]

Answer 1

弄清楚了，这就是代码应该是什么样子的import java.util.ArrayList;import java.util.LinkedList;import java.util.List;import java.util.Scanner;public class Sieve {public static void main(String[] args) {&nbsp; &nbsp; int maxNum;&nbsp; &nbsp; boolean possible = true;&nbsp; &nbsp; String howItsGoing, greatDetail;&nbsp; &nbsp; Scanner scnr = new Scanner(System.in);&nbsp; &nbsp; Scanner scnr2 = new Scanner(System.in);&nbsp; &nbsp; // get upper limit&nbsp; &nbsp; System.out.print("What's the biggest number I should check? ");&nbsp; &nbsp; maxNum = scnr.nextInt();&nbsp; &nbsp; // check for verbose mode&nbsp; &nbsp; System.out.print("Shall I tell you how it's going? ");&nbsp; &nbsp; howItsGoing = scnr2.nextLine().toUpperCase();&nbsp; &nbsp; if (howItsGoing.startsWith("N")) {&nbsp; &nbsp; &nbsp; &nbsp; greatDetail = "N";&nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; System.out.print("Shall I tell you in great detail? ");&nbsp; &nbsp; &nbsp; &nbsp; greatDetail = scnr2.nextLine().toUpperCase();&nbsp; &nbsp; }&nbsp; &nbsp; // create and fill list of possible primes&nbsp; &nbsp; List<Integer> nums = new LinkedList<>();&nbsp; &nbsp; for (int i = 2; i <= maxNum; i++) {&nbsp; &nbsp; &nbsp; &nbsp; nums.add(i);&nbsp; &nbsp; }&nbsp; &nbsp; // create list for the primes&nbsp; &nbsp; List<Integer> primes = new ArrayList<>();&nbsp; &nbsp; // while there are still possible numbers&nbsp; &nbsp; while (possible) {&nbsp; &nbsp; &nbsp; &nbsp; // add the first number from the list of possibles to the list of&nbsp; &nbsp; &nbsp; &nbsp; // primes&nbsp; &nbsp; &nbsp; &nbsp; primes.add(nums.get(0));&nbsp; &nbsp; &nbsp; &nbsp; if (howItsGoing.startsWith("Y")) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.println();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.println();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.print("Found prime: ");&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.printf("%1d ", nums.get(0));&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.println();&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; // remove it and its multiples from the list of possible primes&nbsp; &nbsp; &nbsp; &nbsp; int divisor = nums.get(0);&nbsp; &nbsp; &nbsp; &nbsp; nums.remove(nums.get(0));&nbsp; &nbsp; &nbsp; &nbsp; for (int i = divisor; i <= maxNum; i++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (i % divisor == 0) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (greatDetail.startsWith("Y")) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.println(&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; "&nbsp; &nbsp; Removing " + i + " from possibles");&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; nums.remove((Integer) i);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; System.out.println();&nbsp; &nbsp; &nbsp; &nbsp; if (nums.size() > 0) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (howItsGoing.startsWith("Y")) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.print("Possibles:\n&nbsp; &nbsp; ");&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (int i = 0; i < nums.size(); i++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.printf("%6d ", nums.get(i));&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; if (nums.size() < 1) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; possible = false;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; // print the prime numbers&nbsp; &nbsp; System.out.println();&nbsp; &nbsp; System.out.println("Primes up to " + maxNum);&nbsp; &nbsp; for (int i = 0; i < primes.size(); i++) {&nbsp; &nbsp; &nbsp; &nbsp; System.out.printf("%6d ", primes.get(i));&nbsp; &nbsp; }}}输出What's the biggest number I should check? 20Shall I tell you how it's going? yesShall I tell you in great detail? yesFound prime: 2&nbsp;Removing 2 from possiblesRemoving 4 from possiblesRemoving 6 from possiblesRemoving 8 from possiblesRemoving 10 from possiblesRemoving 12 from possiblesRemoving 14 from possiblesRemoving 16 from possiblesRemoving 18 from possiblesRemoving 20 from possiblesPossibles:&nbsp; &nbsp; &nbsp;3&nbsp; &nbsp; &nbsp; 5&nbsp; &nbsp; &nbsp; 7&nbsp; &nbsp; &nbsp; 9&nbsp; &nbsp; &nbsp;11&nbsp; &nbsp; &nbsp;13&nbsp; &nbsp; &nbsp;15&nbsp; &nbsp; &nbsp;17&nbsp; &nbsp; &nbsp;19&nbsp;Found prime: 3&nbsp;Removing 3 from possiblesRemoving 6 from possiblesRemoving 9 from possiblesRemoving 12 from possiblesRemoving 15 from possiblesRemoving 18 from possiblesPossibles:&nbsp; &nbsp; &nbsp;5&nbsp; &nbsp; &nbsp; 7&nbsp; &nbsp; &nbsp;11&nbsp; &nbsp; &nbsp;13&nbsp; &nbsp; &nbsp;17&nbsp; &nbsp; &nbsp;19&nbsp;Found prime: 5&nbsp;Removing 5 from possiblesRemoving 10 from possiblesRemoving 15 from possiblesRemoving 20 from possiblesPossibles:&nbsp; &nbsp; &nbsp;7&nbsp; &nbsp; &nbsp;11&nbsp; &nbsp; &nbsp;13&nbsp; &nbsp; &nbsp;17&nbsp; &nbsp; &nbsp;19&nbsp;Found prime: 7&nbsp;Removing 7 from possiblesRemoving 14 from possiblesPossibles:&nbsp; &nbsp; 11&nbsp; &nbsp; &nbsp;13&nbsp; &nbsp; &nbsp;17&nbsp; &nbsp; &nbsp;19&nbsp;Found prime: 11&nbsp;Removing 11 from possiblesPossibles:&nbsp; &nbsp; 13&nbsp; &nbsp; &nbsp;17&nbsp; &nbsp; &nbsp;19&nbsp;Found prime: 13&nbsp;Removing 13 from possiblesPossibles:&nbsp; &nbsp; 17&nbsp; &nbsp; &nbsp;19&nbsp;Found prime: 17&nbsp;Removing 17 from possiblesPossibles:&nbsp; &nbsp; 19&nbsp;Found prime: 19&nbsp;Removing 19 from possiblesPrimes up to 20&nbsp;2&nbsp; &nbsp; &nbsp; 3&nbsp; &nbsp; &nbsp; 5&nbsp; &nbsp; &nbsp; 7&nbsp; &nbsp; &nbsp;11&nbsp; &nbsp; &nbsp;13&nbsp; &nbsp; &nbsp;17&nbsp; &nbsp; &nbsp;19&nbsp;

Answer 2

我已经突出显示了错误：&nbsp; &nbsp; // remove it and its multiples from the list of possible primes&nbsp; &nbsp; for(int i=0; i<=maxNum; i++) {&nbsp; &nbsp; &nbsp; &nbsp; if(i % 2 == 0) {&nbsp; // first bug&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; nums.remove(i); // second bug&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }第一个错误是 i % 2 == 0 检查 i 是否是 2 的倍数，但它应该检查它是否是当前素数的倍数。第二个错误是nums.remove(i);是模棱两可的。 声明两种不同的 remove 方法：删除列表中的第 i 个条目，以及 ，删除等于 的条目。由于 a 可以转换为 ，因此两种方法都与参数的类型匹配，但与参数类型更接近，因此被使用，而您可能希望删除（Integer）...您可以通过转换参数来解决此问题：ArrayList<Integer>remove(int)remove(Integer)iintIntegerremove(int)nums.remove((Integer) i);这应该使代码正常工作，但你很快就会意识到代码相当慢。这是因为实际上是一个相当昂贵的操作，因为它涉及迭代整个操作，直到找到要删除。也就是说，对于您淘汰的每个主要候选人，您都会与所有其他主要候选人进行交互。由于其中有很多，因此您的代码将非常慢。remove(Integer)ListInteger解决方案是选择一个支持更有效地按值删除的数据结构。这就是为什么每个人在实现此算法时使用a的原因。boolean[]