我正在嘗試使用 AKS 算法對 16 位長的數字執行素數檢查。我不斷收到錯誤消息。有人可以編譯我的代碼并幫助我了解我在哪里犯了錯誤。（我要編譯的數字示例：1425412525412545。）這是我的 AKSPrime 課程：import java.math.BigInteger;public class AKSPrime{public static void main(String[] args){ AKSPrime p = new AKSPrime(); TextReader k = new TextReader(); System.out.print("Input number for primality testing: "); int i = k.readInt(); System.out.println("Is " + i + " prime? " + p.isPrime(i));}public boolean isPrime(int numberToTest){ boolean prime = true; boolean flag = true; boolean suitableQFound = false; boolean polynomialsCongruent = true; int b, q; int suitableQ; double power; for(int a = 2; a <= Math.sqrt(numberToTest); a++) { b = 2; power = Math.pow(a, b); while(!(power > numberToTest)) { power = Math.pow(a, b); if(power == numberToTest) { prime = false; break; } b++; } } // Algorithm Line 2 int r = 2; // Algorithm Line 3 while( r < numberToTest && flag && !suitableQFound) { //Algorithm Line 4 if(GCD(numberToTest, r) != 1) { return false; } //Algorithm Line 5 if(nonAKSisPrime(r)) { // Algorithm Line 6 q = largestPrimeFactor(r - 1); double sqrtR = Math.sqrt(r); double logN = Math.log(numberToTest)/Math.log(2); // Algorithm Line 7 if( q >= 4*Math.sqrt(r)*Math.log(numberToTest)/Math.log(2) ) { // Algorithm Line 8 suitableQ = q; suitableQFound = true; } } // Algorithm Line 9 if(!suitableQFound) r++; }
2 回答
catspeake
TA貢獻1111條經驗 獲得超0個贊
AKS 素性測試的實現僅限于使用 32 位數據類型，它可以存儲最多2,147,483,647. 你的號碼比那個大很多，所以沒有正確閱讀。
聽起來很容易解決，我們應該能夠將所有出現的int,更改為，long因為long數據類型可以存儲非常大的數字。不幸的是，這行不通，因為我們仍然受到 Java 中 32 位數組的最大大小的限制。因此，不深入研究不安全的內存訪問是非常不切實際的。
如果要檢查大數字的素數，可以像這樣修改代碼：
替換main為：
public static void main(String[] args)
{
AKSPrime p = new AKSPrime();
TextReader k = new TextReader();
System.out.print("Input number for primality testing: ");
long i = k.readLong();
System.out.println("Is " + i + " prime? " + p.nonAKSisPrime(i));
}
用這個替換nonAKSisPrime函數：
private boolean nonAKSisPrime(long x)
{
long f = 2;
boolean result = true;
long s = (long)Math.sqrt(x);
while(f <= s && result)
{
if(x % f == 0)
result = false;
f++;
}
return result;
}
并將這個新函數添加到TextReader，讀取long值：
public long readLong()
{
long result = 0;
do // keep on trying until a valid long is entered
{
try
{
result = Long.parseLong(readWord());
break; // result is good, jump out of loop down to return result;
}
catch (Exception e)
{
if(rePrompting)
System.out.println("Invalid long. Try again.");
else
{
error( "readLong" );
break;
}
}
} while( true );
return result;
}
繁星淼淼
TA貢獻1775條經驗 獲得超11個贊
恐怕您的意思是 16字節整數，而不是bit。一個javaint是4字節32位，一個long8字節64位。
1425412525412545可能適合 long，當然不是 int，也許您BigInteger原則上應該使用來覆蓋完整的 16 個字節。
由于這不再是原始類型，因此需要更多的編寫。
添加回答
舉報
0/150
提交
取消