Блог

Главная - Вопросы по программированию - Решетка Эратосфена (С ИСПОЛЬЗОВАНИЕМ LINKEDLIST)

Решетка Эратосфена (С ИСПОЛЬЗОВАНИЕМ LINKEDLIST)

#java #list #sieve-of-eratosthenes #sieve

#java #Список #решетка эратосфена #решетка

Вопрос:

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

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

В принципе, 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);


}

}

игнорируйте исходящую строку и 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]

Ответ №1:

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

     // 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 проверяет, является ли i кратным 2, но он должен проверять, кратно ли оно текущему простому числу.

Вторая ошибка заключается в том, что 

 nums.remove(i);

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

 nums.remove((Integer) i);

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

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

Комментарии:

1. Спасибо, я это исправил, но прямо сейчас я проверяю, делится ли первое число на 2, что, очевидно, верно, поэтому оно удаляет 2, что насчет остальных чисел, как бы я это сделал? а что касается эффективности, я знаю, что она медленная, я действительно просто практикую списки перед экзаменом. я создавал случайные программы

Ответ №2:

Разобрался, вот как должен выглядеть код

 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(" ", 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("m ", 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("m ", 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