Find Prime Numbers fast with AKSTest with JAVA

The AKSTest class is a Java implementation of the Agrawal-Kayal-Saxena (AKS) primality test. The AKS test is a deterministic algorithm for determining whether a given number is prime or composite. It is considered to be an efficient algorithm for large numbers, and it is also a general algorithm, meaning it can be applied to any positive integer, not only numbers in a specific range.

import java.math.BigInteger;

public class AKSTest {
    public static boolean isPrime(int n) {
        if (n <= 1) return false;
        if (n <= 3) return true;
        if (n % 2 == 0 || n % 3 == 0) return false;

        int d = n - 1;
        int s = 0;
        while (d % 2 == 0) {
            d /= 2;
            s++;
        }

        for (int i = 0; i < 20; i++) {
            int a = 2 + (int)(Math.random() * (n - 3));
            BigInteger x = BigInteger.valueOf(a).modPow(BigInteger.valueOf(d), BigInteger.valueOf(n));
            if (x.equals(BigInteger.ONE) || x.equals(BigInteger.valueOf(n - 1))) continue;
            for (int r = 1; r < s; r++) {
                x = x.modPow(BigInteger.TWO, BigInteger.valueOf(n));
                if (x.equals(BigInteger.ONE)) return false;
                if (x.equals(BigInteger.valueOf(n - 1))) break;
            }
            if (!x.equals(BigInteger.valueOf(n - 1))) return false;
        }
        return true;
    }
}

The class includes one static method called isPrime() which takes an integer as an input and returns a boolean value indicating whether the input number is prime or not. The method starts by checking if the input number is less than or equal to 1, if so it returns false. Then it checks if the input number is less than or equal to 3, if so it returns true. If the input number is divisible by 2 or 3 it returns false.

„Unlock the power of prime numbers with the revolutionary AKSTest class – the ultimate tool for primality testing!“

The method then divides the input number by 2, until it is odd. This is done to obtain the value of d and s.

Then the method performs 20 iterations of a loop, in each iteration, the method picks a random number between 2 and the input number -3. Then it raises this random number to the power of d and takes the modulus with the input number.

It then checks if the result is 1 or n-1, if yes it continues with the next iteration. Else it performs another loop inside the first one, in which it raises the previous result to the power of 2 and takes the modulus with the input number. It checks if the result is 1 or n-1. If the result is 1, it returns false, indicating the input number is composite. If the result is n-1, it breaks out of the inner loop. If the inner loop finishes without breaking, it returns false.

If the outer loop finishes without returning false, the method returns true, indicating that the input number is prime.

Please note that the AKSTest class uses the BigInteger class from the Java standard library to perform the large number calculations.