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){&nbsp; &nbsp; AKSPrime p = new AKSPrime();&nbsp; &nbsp; TextReader k = new TextReader();&nbsp; &nbsp; System.out.print("Input number for primality testing: ");&nbsp; &nbsp; long i = k.readLong();&nbsp; &nbsp; System.out.println("Is " + i + " prime? " + p.nonAKSisPrime(i));}用这个替换nonAKSisPrime函数：private boolean nonAKSisPrime(long x){&nbsp; &nbsp; long f = 2;&nbsp; &nbsp; boolean result = true;&nbsp; &nbsp; long s = (long)Math.sqrt(x);&nbsp; &nbsp; while(f <= s && result)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; if(x % f == 0)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; result = false;&nbsp; &nbsp; &nbsp; &nbsp; f++;&nbsp; &nbsp; }&nbsp; &nbsp; return result;}并将这个新函数添加到TextReader，读取long值：&nbsp; public long readLong(){&nbsp;&nbsp; &nbsp; long result = 0;&nbsp; &nbsp; do // keep on trying until a valid long is entered&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; try&nbsp;&nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; result = Long.parseLong(readWord());&nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; // result is good, jump out of loop down to return result;&nbsp;&nbsp; &nbsp; &nbsp; }&nbsp;&nbsp; &nbsp; &nbsp; catch (Exception e)&nbsp;&nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; if(rePrompting)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.println("Invalid long. Try again.");&nbsp; &nbsp; &nbsp; &nbsp; else&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; error( "readLong" );&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; } while( true );&nbsp; &nbsp; return result;&nbsp; }

Answer 2

恐怕您的意思是 16字节整数，而不是bit。一个javaint是4字节32位，一个long8字节64位。1425412525412545可能适合 long，当然不是 int，也许您BigInteger原则上应该使用来覆盖完整的 16 个字节。由于这不再是原始类型，因此需要更多的编写。