Как определить, является ли число простым

Question

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

Вот мой код:

public static void main(String[] args) { 
    // Declare Variables 
    int randomNumbers = 0; 
    int sum = 0; 
    //Loop for number generation and print out numbers 
    System.out.print("The five random numbers are: "); 
    for (int i = 0; i <= 4; i++) 
    { 
     randomNumbers = (int)(Math.random()*20); 
     sum += randomNumbers; 

     if (i == 4) { 
      System.out.println("and " + randomNumbers + "."); 
     } 
     else { 
      System.out.print(randomNumbers + ", "); 
     } 
    } 
    //Display Sum 
    System.out.println("\nThe sum of these five numbers is " + sum + ".\n"); 

    //Determine if the sum is prime and display results 
    for(int p = 2; p < sum; p++) { 
     if(sum % p == 0) 
      System.out.println("The sum is not a prime number."); 
     else 
      System.out.println("The sum is a prime number."); 
     break; 
     } 
    } 


} 

Теперь моя проблема, если число заканчивается время что-то вроде 9, это будет сказать, что это простое число, что это не так. Я думаю, что проблема заключается в том, что прерывание останавливает его после одного цикла, поэтому он не увеличивает переменную p, так что только тестирование делит на 2 (я думаю). Но если я удалю точку прерывания, она распечатает «Сумма - это не простое число» на каждом проходе до выхода из цикла. Не уверен, что делать здесь.

Answer 1

Ваш метод поиска, если ваш номер является простым, является правильным методом. Чтобы сделать это так, чтобы он не постоянно печатал, является ли число простым, вы можете иметь внешнюю переменную, представляющую, является ли число простым.

Такие, как

boolean prime = true; 
    for (int p = 2; p < sum; p++) { 
     if (sum % p == 0) { 
      prime = false; 
      break; 
     } 
    } 
    if (prime) 
     System.out.println("The sum is a prime number."); 
    else 
     System.out.println("The sum is not a prime number."); 

Делая этот метод программа будет считать, что число является простым, пока он не докажет, что неправильно. Поэтому, когда он обнаруживает, что он не является простым, он устанавливает переменную в false и выходит из цикла.

Затем после завершения цикла вам просто нужно распечатать, было ли это число простым.

Способ, которым вы могли бы сделать этот цикл быстрее, - это перейти от p = 2 к, когда p = квадратный корень из суммы. Таким образом, используя этот метод, ваш цикл будет выглядеть следующим образом:

double sq = Math.sqrt((double)sum); 
    for (int p = 2; p < sq; p++) { 
     //Rest of code goes here 
    } 

Надеется, что это помогает

Answer 2

Вам нужно хранить или нет числа является простым в булевом снаружи цикла:

//Determine if the sum is prime and display results 
boolean isPrime = true; 
for(int p = 2; p < sum; p++) { 
    if(sum % p == 0){ 
     isPrime = false; 
     break; 
    } 
} 
if(isPrime){ 
    System.out.println("The sum is a prime number."); 
} else { 
    System.out.println("The sum is not a prime number."); 
} 

Answer 3

Вы правы, в настоящее время ваши тесты кода делятся на два, а команда break останавливается после одного цикла.

После первого хода вашей петли (p == 2) break всегда будет останавливать цикл.

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

boolean isPrime=true; 
for(int p = 2; p < sum; p++) { 
    if(sum % p == 0) { 
     isPrime=false; 
     System.out.println("The sum is not a prime number."); 
     break; 
    } 
} 
if (isPrime) 
    System.out.println("The sum is a prime number."); 

Этот код может быть улучшена для повышения эффективности и кода элегантности.

Для эффективности вам не нужно проверять делимость на все числа, меньшие суммы, достаточно проверить все числа, меньшие квадратным корнем суммы.

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

Вот пример, который реализует оба варианта.

// tests if n is prime 
public static boolean isPrime(int n) { 
    if (n<2) return false; 
    for(int p = 2; p < Math.sqrt(n); p++) { 
     if(n % p == 0) return false; // enough to find one devisor to show n is not a prime 
    } 
    return true; // no factors smaller than sqrt(n) were found 
} 

public static void main(String []args){ 
    ... 
    System.out.println("sum is "+ sum); 
    if (isPrime(sum)) 
     System.out.println("The sum is a prime number."); 
    else 
     System.out.println("The sum is not a prime number."); 
} 

Answer 4

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

private static boolean isPrime(int iNum) { 
boolean bResult = true; 
if (iNum <= 1 || iNum != 2 && iNum % 2 == 0) { 
    bResult = false; 
} else { 
    int iSqrt = (int) Math.sqrt(iNum); 
    for (int i = 3; i < iSqrt; i += 2) { 
    if (iNum % i == 0) { 
     bResult = false; 
     break; 
    } 
    } 
} 
return bResult; 
} 

Преимущества выше code-:

1. Он будет работать для отрицательных чисел и 0 & 1 а.
2. Он будет запускать цикл for только для нечетных чисел.
3. Это будет увеличивать переменную в for цикла на 2, а не 1.
4. Это будет итерации цикла for только ДО квадратный корень из числа, а не Шифрование до числа.

Explanation-:

Я упомянул четыре точки, над которой я объясню один за другим. Код должен быть надлежащим образом записан для неверных вводах, а не только для действительного ввода. Какие бы ответы ни были написаны до сих пор, они ограничены допустимым диапазоном ввода, в котором номер iNum >=2.

Мы должны знать, что только нечетные числа могут быть простые, Примечание-: 2 является единственной даже простым. Таким образом, мы не должны запускать цикл for для четных чисел.

Мы не должны запускать цикл for для четных значений его переменной i, поскольку мы знаем, что четные числа могут быть разделены четными числами. Я уже упоминал в вышеприведенном пункте, что только нечетные числа могут быть целыми, кроме 2 как четные. Поэтому нет необходимости запускать код внутри for цикл для четных значений переменной i в for.

Мы должны повторить for петля только до квадратный корень номера, а не выше. Немногие из ответов внесли этот момент, но я все же думал об этом упомянуть.

Answer 5

Маленькие простые числа

Использование Apache Commons Mathтест на простоту, метод связан с простыми числами в диапазоне int. Вы можете найти исходный код на GitHub.

<dependency> 
    <groupId>org.apache.commons</groupId> 
    <artifactId>commons-math3</artifactId> 
    <version>3.6.1</version> 
</dependency> 

// org.apache.commons.math3.primes.Primes 
Primes.isPrime(2147483629); 

Он использует вероятностный тест Миллера-Рабина таким образом, что результат гарантирован: он использует нововведений простых чисел в качестве последовательного базы (см Справочник по прикладной криптографии Menezes, table 4.1/страница 140) ,

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

Если вы ищете простые числа больше, чем Integer.MAX_VALUE:

1. Используйте BigInteger#isProbablePrime(int certainty) предварительно проверить главным кандидатом

   Возвращает истину, если этого BigInteger вероятно, является простым, false, если это определенно композитный. Если определенность ≤ 0, возвращается значение true. Параметры: определенность - мера неопределенности, которую вызывающий абонент согласен терпеть: если вызов возвращает true, вероятность того, что этот BigInteger просто превосходит (1 - 1/2certainty). Исполнение время этого метода пропорционально значению этого параметра.

2. Следующее использование "AKS Primality Test", чтобы проверить, действительно ли кандидат является простым.