AKS-无法编译 16 位整数进行素数检查

Question

我正在尝试使用 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++;    }

Answer 1

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;

  }

Answer 2

恐怕您的意思是 16字节整数，而不是bit。一个javaint是4字节32位，一个long8字节64位。

1425412525412545可能适合 long，当然不是 int，也许您BigInteger原则上应该使用来覆盖完整的 16 个字节。

由于这不再是原始类型，因此需要更多的编写。