Рельеф решета эрастотенов

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

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

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

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

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 + ", "); 
     } 
    } 
} 

Answer 2

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

Ниже приведен пример раствора (который опирается на 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; 
    } 
}