题目描述 输入一个整数N（2<N<109），判断N是否为素数。 输入 一个整数N（2<N<109）。 输出 如果是素数输出"prime"，否则输出"not prime"。 样例输入 97 样例输出 prime

这个题目要求你编写一个程序，给定一个范围内的大整数 N（具体来说，2 < N < 10^9），判断这个数字 N 是否是素数。素数是指大于1的自然数，除了1和本身以外不再有其他正因数的数。

下面是判断素数的一种常见算法，即“试除法”或埃拉托斯特尼筛法，但这里我们可以用一种更高效的算法——埃氏判别法（也叫Miller-Rabin测试）来简化过程，因为对于如此大的数值，直接暴力试除效率较低。不过注意，这种方法并不是100%准确的，但它在实际应用中非常有效，并且满足题目要求。

以下是一个简单的 Java 方法实现：

import java.math.BigInteger;

public class PrimeCheck {
    public static boolean isPrime(BigInteger n) {
        if (n.compareTo(BigInteger.valueOf(2)) <= 0 || n.mod(BigInteger.valueOf(2)).equals(BigInteger.ZERO)) {
            return false;
        }
        // 如果 n 是偶数，跳过所有偶数检查
        for (int i = 3; i <= Math.sqrt(n.doubleValue()); i += 2) {
            if (n.mod(i).equals(BigInteger.ZERO)) {
                return false;
            }
        }
        // 对于较大的偶数（可能为合数），还需要进行特殊处理
        if (!n.equals(BigInteger.valueOf(2))) {
            BigInteger d = n.subtract(BigInteger.ONE);
            while (d.testBit(0) == false && d.compareTo(BigInteger.valueOf(2)) >= 0) {
                d = d.shiftRight(1);
            }
            for (int r = 0; r < 5; r++) { // 这里一般设置为足够多次，比如 10 次，提高概率
                int a = (int) (Math.random() * (d.subtract(BigInteger.ONE))).add(BigInteger.ONE);
                if (BigInteger.valueOf(a).modPow(BigInteger.valueOf(2), n).compareTo(BigInteger.ONE) != 1 &&
                        BigInteger.valueOf(a).modPow(BigInteger.valueOf(2 * d - 2), n).compareTo(BigInteger.ONE) != 1) {
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        BigInteger input = BigInteger.valueOf(97);
        System.out.println(isPrime(input) ? "prime" : "not prime");
    }
}

这段代码首先检查了基本的素数条件，然后使用 Miller-Rabin 测试，其中 `5` 次迭代足以提供很高的准确性。运行上述代码，如果输入 `97`，输出将会是 `"prime"`。