Java Array сохраняет простые числа и использует его для поиска следующего простого

Question

У меня есть небольшая проблема, понимающая, что мой учитель хочет, чтобы я сделал. То, что я сделал, - это код, который сохраняет мне все основные числа в массиве, которые могут отображаться. Но теперь он хочет, чтобы я «оптимизировал» код, поскольку, насколько я понимаю, попытайтесь разделить число только на числа, которые являются первичными. Например: если у меня 2,3,5, то следующее число должно быть простым, это число, которое не делится ни на одно из них. Поэтому мне не нужно пытаться 2,3,4,5, но только 2,3,5 (числа, которые у меня есть в массиве). И например: 2,3,4,5,7 - простые числа, 10 - это не потому, что он делит на 2, тогда он должен прыгать на следующий номер.

public static void main(String[] args) { 
    String introducedNumber = JOptionPane.showInputDialog("Introduce a number"); //with JOptionPane imported will ask you a small box for a number 
    int number, divider, numberDividing; //declaring the int's 

    number = Integer.parseInt(introducedNumber); //converting the input to a int 
    int x = 0; //starting X to 0 since its 1st array position 
    int[] arrayPrime = new int[number]; //declaring and creating an array 
    for (divider = 1; divider <= number; divider++) { //for to run till numbers 
     //for that checks if the number divides by any other than himself 
     for (numberDividing = 2; (numberDividing < divider) && (divider % numberDividing != 0); numberDividing++) { 
     } 

     if (numberDividing >= divider) { 
      arrayPrime[x] = divider; 
      x++; 
     } 
    } 
    for (int i = 0; i < x; i++) { 
     System.out.println(arrayPrime[i]); 
    } 

} 

}

Answer 1

В данный момент ваш код, чтобы проверить, является ли число простым является:

for (numberDividing = 2; (numberDividing < divider) && (divider % numberDividing != 0); numberDividing++) { 
    } 

    if (numberDividing >= divider) { 
     arrayPrime[x] = divider; 
     x++; 
    } 

Так он проверяет все цифры от 2 до последнего штриха. Но нет необходимости в этом: нужно только проверить простые числа, которые у вас уже есть в вашем массиве.

Чтобы сделать ваш код более читабельным, я предлагаю перевести свой чек на отдельный частный метод. Я также переименовал x в primeCount:

private boolean isPrime(int number) { 
    for (int i = 0; i < primeCount; i++) { 
     if (number % arrayPrime[i] == 0) 
      return false; 
    } 
    return true; 
} 

Тогда ваш код вызова становится:

for (int divider = 2; divider <= number; divider++) { 
    if (isPrime(divider)) 
     arrayPrime[primeCount++] = divider; 
} 

Существует еще одна довольно тривиальная оптимизации вы можете сделать. Вам не нужно, чтобы проверить все простые числа, которые больше, чем квадратный корень из числа теста, потому что вы уже проверили более мелкие факторы в этой точке:

private boolean isPrime(int number) { 
    for (int i = 0; i < primeCount; i++) { 
     int prime = arrayPrime[i]; 
     if (prime * prime > number) 
      break; 
     else if (number % prime == 0) 
      return false; 
    } 
    return true; 
} 

Если вы не хотите использовать отдельный метод , то:

for (int divider = 2; divider <= number; divider++) { 
    boolean isPrime = true; 
    for (int i = 0; i < primeCount && isPrime; i++) { 
     isPrime = number % arrayPrime[i] > 0; 
    } 
    if (isPrime) 
     arrayPrime[primeCount++] = divider; 
} 

И, для вашего будущего исследования, здесь более элегантный способ для достижения того же результата, используя простое число генератора:

public class PrimeGenerator { 
    private long current = 1; 
    private final List<Long> primes = new ArrayList<>(); 

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

Answer 2

вы были правы, что вам нужно только разделить новые числа, ранее обнаруженные штрихи. То, что я делаю ниже, - это просто перебрать все обнаруженные простые числа и использовать логическое значение для отслеживания, если каждое число является простым. Я также использую ArrayList вместо массива, так что в вашем исходном массиве не так много неиспользуемых блоков. Надеюсь это поможет!

ArrayList<Integer> arrayPrime = new ArrayList<Integer>(); //use array list instead of static array 
arrayPrime.add(2); //seed first prime number 
boolean isPrime; //boolean to determine if prime 

for (divider = 3; divider <= number; divider++) { //loop up to input number, starting at 3 

    isPrime = true; //initialize true for each new number 

    for (i = 0; i < arrayPrime.size(); i++) { //loop through each previous prime 

     if (divider % arrayPrime[i] == 0) { //see if number is divisible by previous prime 
      isPrime = false; 
      break; //break out of loop 
     } 
    } 

    if(isPrime){ //if it did not divide evenly, it is prime 
     ArrayPrime.add(divider); 
    } 
} 

System.out.println(list);