Сито Эратосфена (ИСПОЛЬЗУЯ ССЫЛКУ)

Question

Я пытаюсь выяснить, как я буду манипулировать списками, чтобы найти все простые числа до числа, предоставленного пользователем, у меня есть список шагов, которым я пытаюсь следовать, которые

создать и заполнить список возможных простых чисел

В основном это arrayList, который содержит все числа до указанного числа, у меня эта часть сделана

создать список для простых чисел

У меня есть эта часть вниз

пока возможны номера

То есть список возможных простых чисел не пуст.

добавить первое число из списка возможных в список простых чисел

Снял эту часть тоже

удалить его и его кратные из списка возможных простых чисел

это то место, где я начинаю немного ошеломляться, я думал, что у меня есть эта часть, но я получаю ошибку, я не знаю почему.

печать простых чисел

вывести список простых чисел, по сути просто 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, я добавлю их позже.

Как мне заставить эту программу работать правильно, у каждого другого вопроса есть решение в логическом массиве, а это не то, что я хочу. Есть идеи?

OUTPUT

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) {
    int maxNum;
    boolean possible = true;
    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();

    if (howItsGoing.startsWith("N")) {
        greatDetail = "N";
    } else {
        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
    while (possible) {
        // add the first number from the list of possibles to the list of
        // primes

        primes.add(nums.get(0));

        if (howItsGoing.startsWith("Y")) {
            System.out.println();
            System.out.println();
            System.out.print("Found prime: ");
            System.out.printf("%1d ", nums.get(0));
            System.out.println();
        }
        // remove it and its multiples from the list of possible primes
        int divisor = nums.get(0);

        nums.remove(nums.get(0));

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

            if (i % divisor == 0) {
                if (greatDetail.startsWith("Y")) {
                    System.out.println(
                            "    Removing " + i + " from possibles");
                }
                nums.remove((Integer) i);
            }

        }
        System.out.println();
        if (nums.size() > 0) {
            if (howItsGoing.startsWith("Y")) {
                System.out.print("Possibles:\n    ");
                for (int i = 0; i < nums.size(); i++) {
                    System.out.printf("%6d ", nums.get(i));
                }

            }
        }
        if (nums.size() < 1) {
            possible = false;
        }
    }

    // print the prime numbers
    System.out.println();
    System.out.println("Primes up to " + maxNum);
    for (int i = 0; i < primes.size(); i++) {
        System.out.printf("%6d ", primes.get(i));
    }

}
}

выход

What's the biggest number I should check? 20
Shall I tell you how it's going? yes
Shall I tell you in great detail? yes


Found prime: 2 
Removing 2 from possibles
Removing 4 from possibles
Removing 6 from possibles
Removing 8 from possibles
Removing 10 from possibles
Removing 12 from possibles
Removing 14 from possibles
Removing 16 from possibles
Removing 18 from possibles
Removing 20 from possibles

Possibles:
     3      5      7      9     11     13     15     17     19 

Found prime: 3 
Removing 3 from possibles
Removing 6 from possibles
Removing 9 from possibles
Removing 12 from possibles
Removing 15 from possibles
Removing 18 from possibles

Possibles:
     5      7     11     13     17     19 

Found prime: 5 
Removing 5 from possibles
Removing 10 from possibles
Removing 15 from possibles
Removing 20 from possibles

Possibles:
     7     11     13     17     19 

Found prime: 7 
Removing 7 from possibles
Removing 14 from possibles

Possibles:
    11     13     17     19 

Found prime: 11 
Removing 11 from possibles

Possibles:
    13     17     19 

Found prime: 13 
Removing 13 from possibles

Possibles:
    17     19 

Found prime: 17 
Removing 17 from possibles

Possibles:
    19 

Found prime: 19 
Removing 19 from possibles


Primes up to 20
 2      3      5      7     11     13     17     19 

Answer 2

Я выделил ошибки:

    // remove it and its multiples from the list of possible primes
    for(int i=0; i<=maxNum; i++) {
        if(i % 2 == 0) {  // first bug
            nums.remove(i); // second bug
        }
    }

Первая ошибка заключается в том, что i% 2 == 0 проверяет, является ли я кратным 2, но оно должно проверять, является ли оно кратнымтекущее простое число.

Вторая ошибка в том, что

nums.remove(i);

неоднозначно.ArrayList<Integer> объявляет два разных метода удаления: remove(int), который удаляет i-ую запись в списке, и remove(Integer), который удаляет запись, равную i.Поскольку int можно преобразовать в Integer, оба метода соответствуют типу вашего аргумента, но remove(int) более точно соответствует типу аргумента и поэтому используется, в то время как вы, вероятно, хотели удалить (Integer) ... выэто можно исправить, приведя аргумент:

nums.remove((Integer) i);

Это должно заставить код работать правильно, но вы скоро поймете, что код довольно медленный.Это потому, что remove(Integer) на самом деле является довольно дорогостоящей операцией, поскольку включает в себя итерацию по всему List до тех пор, пока не будет найден Integer для удаления.То есть, для каждого выбранного вами кандидата вы взаимодействуете со всеми остальными кандидатами.Поскольку их очень много, ваш код будет очень медленным.

Решение состоит в том, чтобы выбрать структуру данных, которая более эффективно поддерживает удаление по значению.И именно поэтому каждый использует boolean[], когда они реализуют этот алгоритм.