我正在嘗試使用 AKS 算法對(duì) 16 位長的數(shù)字執(zhí)行素?cái)?shù)檢查。我不斷收到錯(cuò)誤消息。有人可以編譯我的代碼并幫助我了解我在哪里犯了錯(cuò)誤。（我要編譯的數(shù)字示例：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貢獻(xiàn)1111條經(jīng)驗(yàn) 獲得超0個(gè)贊
AKS 素性測試的實(shí)現(xiàn)僅限于使用 32 位數(shù)據(jù)類型，它可以存儲(chǔ)最多2,147,483,647. 你的號(hào)碼比那個(gè)大很多，所以沒有正確閱讀。
聽起來很容易解決，我們應(yīng)該能夠?qū)⑺谐霈F(xiàn)的int,更改為，long因?yàn)閘ong數(shù)據(jù)類型可以存儲(chǔ)非常大的數(shù)字。不幸的是，這行不通，因?yàn)槲覀內(nèi)匀皇艿?Java 中 32 位數(shù)組的最大大小的限制。因此，不深入研究不安全的內(nèi)存訪問是非常不切實(shí)際的。
如果要檢查大數(shù)字的素?cái)?shù)，可以像這樣修改代碼：
替換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));
}
用這個(gè)替換nonAKSisPrime函數(shù)：
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;
}
并將這個(gè)新函數(shù)添加到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貢獻(xiàn)1775條經(jīng)驗(yàn) 獲得超11個(gè)贊
恐怕您的意思是 16字節(jié)整數(shù)，而不是bit。一個(gè)javaint是4字節(jié)32位，一個(gè)long8字節(jié)64位。
1425412525412545可能適合 long，當(dāng)然不是 int，也許您BigInteger原則上應(yīng)該使用來覆蓋完整的 16 個(gè)字節(jié)。
由于這不再是原始類型，因此需要更多的編寫。
添加回答
舉報(bào)
0/150
提交
取消