Сито из эрастотена

Question

Установите для печати всех ложных значений, которые являются простыми числами, однако из 25 он печатает. 3, 5, 7, 8, 9, 11, 13, 14, 15, 17, 19, 20, 21, 23, 24, не знаю, почему некоторые из них проскальзывают. Любое понимание этого вопроса было бы хорошо.

Или просто указывает мне в направлении записи. Почему не простые числа, такие как 8, печатаются?

import java.util.Arrays;
import java.util.Scanner;
class Sieve {
      public static void main(String args[]) {
              Scanner inputScanner;
              inputScanner = new Scanner(System.in);
              //determine max value
              System.out.println("I will determine all the primality of a set of numbers, enter the max");
              int n = Integer.parseInt (inputScanner.nextLine());
              boolean[] truedBooleanArray = calcBooleanMax (n);
              //call upon function to check primality
              boolean [] primeNumbers = calcPrimality (truedBooleanArray);
              // call upon function to print out prime numbers
              printPrimes(primeNumbers);
      }

      public static boolean[] calcBooleanMax(int maxNumber) {
              boolean [] maxNumberArray = new boolean [maxNumber];
              maxNumberArray[0] = false;
              maxNumberArray[1] = false;
              //asigns  1, 0 to false
              //change all boleans within array from false to true!
              for(int i=1; i < maxNumber; i++) {
                      maxNumberArray [i] = true;
              }
              return maxNumberArray;
      }

      public static boolean[] calcPrimality(boolean [] truedBooleans) {
              for(int i = 2; i <=truedBooleans.length; i++) {
                      //check every number greater than 1 for primality.
                      if (truedBooleans[i-1]) {

                      }
                      //finds multiples and makes sure they arent stored
                      for(int j = 2*i; j <= truedBooleans.length; j+= i) {
                              truedBooleans[j-1] = false;
                      }
              } 
              return truedBooleans;
      }

      public static void printPrimes(boolean [] thePrimeNumbers){
              System.out.println("The prime numbers are [");
              for(int i = 2; i<thePrimeNumbers.length; i++) {
                      if(thePrimeNumbers[i] == false ) {
                              System.out.print(i + ", ");
                      }
              }
      }
}

Answer 1

Более простое решение - менее буквальная интерпретация алгоритма. Вместо того, чтобы хранить буквальный список логических значений, вы можете сохранить список текущих простых чисел. Это делает код проще и легче для чтения.

Вот пример решения (которое основано на потоках Java 8):

class Sieve {
    private long current = 2;
    private final List<Long> primes = new ArrayList<>();

    public long nextPrime() {
        while (primes.stream().anyMatch(p -> current % p == 0))
            current++;
        primes.add(current);
        return current;
    }
}

Answer 2

У вас есть несколько ошибок.

• Массив должен быть на один больше указанного максимума
• Вы случайно добавляете один обратно в сито при инициализации
• При удалении множества из сита, вы должны сначала убедиться, что начальное число "i" все еще находится в сите
• Вы хотите напечатать элементы, которые все еще находятся на сите, поэтому печатайте, когда значение true, а не false

Вот фиксированный код

public static boolean[] calcBooleanMax(int maxNumber) {
    boolean [] maxNumberArray = new boolean [maxNumber+1];
    maxNumberArray[0] = false;
    maxNumberArray[1] = false; 
    //asigns  1, 0 to false
    //change all boleans within array from false to true!
    for(int i=2;i < maxNumber+1; i++) {
        maxNumberArray [i] = true;

    }
    return maxNumberArray;
}

public static boolean[] calcPrimality(boolean [] truedBooleans){
    for(int i = 2; i <truedBooleans.length; i++) {
        if(truedBooleans[i]) {
            //finds multiples and makes sure they arent stored
            for(int j = 2*i; j < truedBooleans.length; j+= i) {
                truedBooleans[j] = false;
            }
        }
    }
    return truedBooleans;
}


public static void printPrimes(boolean [] thePrimeNumbers){
    System.out.println("The prime numbers are [");
    for(int i = 2;i<thePrimeNumbers.length;i++) {
        if(thePrimeNumbers[i] ) {
            System.out.print(i + ", "); 
        }
    }
}