我有一個關于不久前在這里給出的答案的問題。
我在附加的代碼中自己想出了相同的答案，但我試圖理解為什么我需要將輸入數字除以 2（第 10 行），而不僅僅是讓回圈運行直到輸入的值達到的數量。
1 import java.util.Scanner;
2 public class numIsPrime {
3 public static void main(String[] args) {
4 Scanner sc = new Scanner(System.in);
5 int i = 2;
6 boolean isPrime = true;
7 System.out.println("Enter a number");
8 int num = sc.nextInt();
9
10 while (i < num ) // (i <= num / 2)
11 {
12 if (num % i == 0)
13 isPrime = false;
14 i ;
15 }
16
17 if (isPrime)
18 System.out.println(num " is a prime number");
19 else // !isPrime
20 System.out.println(num " isn't a prime number");
21
22 }
23 }
uj5u.com熱心網友回復：
正如評論中提到的，除以 2 是減少檢查次數的最簡單優化，但是，現有代碼存在一些問題（例如，回傳true0 和 1 不是質數）并且可以進一步優化：
isPrime設定為立即中斷/結束回圈false- 通過增加 2 跳過偶數
- 計算直至
i * i <= num
如果達到此限制，這意味著沒有因素i的num范圍內已被發現[2, num/i]，因此被素數的定義，所有范圍內的剩余數量[num/i, num]是沒有的因素num，因此num是素數。
Scanner sc = new Scanner(System.in);
System.out.println("Enter a number");
int num = sc.nextInt();
boolean isPrime = num % 2 != 0 || num == 2;
int i = 3;
while (isPrime && i * i <= num) {
if (num % i == 0)
isPrime = false;
i = 2; // skip even numbers
}
if (isPrime)
System.out.println(num " is a prime number");
else
System.out.println(num " isn't a prime number");
如果像排除偶數一樣排除 3 的整除數（3 除外），則可以進行更多優化，然后從 5 繼續搜索并且素數的候選符合6n ± 1規則（例如，5 = 6 - 1, 7 = 6 1、11 = 12 - 1、13 = 12 1 等）：
boolean isPrime = (num % 2 != 0 || num == 2) && (num % 3 != 0 || num == 3);
int i = 5;
int d = 2;
while (isPrime && i * i <= num) {
if (num % i == 0)
isPrime = false;
i = d; // check only non-even numbers
d = 6 - d; // switch 2 to 4 and back to 2
}
uj5u.com熱心網友回復：
這是計算一個整數n是否可能是素數的最簡單方法：
public static boolean isPrime (int n) {
if (n < 2) return false;
BigInteger bigInt = BigInteger.valueOf(n);
return bigInt.isProbablePrime(100);
}
您可以在回圈中插入此函式呼叫，您可以在其中每次迭代傳遞一個新數字。我使用BigIntegerJava 提供的實作來進行計算，而不是自己撰寫。除非這是一項家庭作業并且您需要撰寫自己的演算法，否則我會使用此解決方案。
然后可以使用此基本方法計算其他型別的素數。可以在此處找到完整的答案。
更新：
該int引數BigInteger.isProbablePrime(int)是呼叫者愿意忍受的不確定性的度量。數字越大，它執行得越“慢”（但越確定）。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/394355.html