写一个Java版本的欧拉筛，来判断一个20位数字是否是质数

由于20位数字太大，我们需要使用BigInteger类来处理，以下是Java版本的欧拉筛：

import java.math.BigInteger;

public class EulerSieve {
public static boolean isPrime(BigInteger n) {
if (n.compareTo(BigInteger.valueOf(2)) < 0) return false;
if (n.compareTo(BigInteger.valueOf(2)) == 0) return true;
if (n.mod(BigInteger.valueOf(2)).equals(BigInteger.ZERO)) return false;

int bitLength = n.bitLength();
BigInteger a = BigInteger.valueOf(2);
for (int i = 0; i < bitLength; i++) {
if (a.modPow(n.subtract(BigInteger.ONE), n).equals(BigInteger.ONE)) {
if (!a.equals(BigInteger.valueOf(2)) && !a.equals(BigInteger.valueOf(3))) {
return false;
}
}
a = a.add(BigInteger.ONE);
}
return true;
}

public static BigInteger eulerSieve(int n) {
int[] primes = new int[n + 1];
boolean[] isPrime = new boolean[n + 1];
int cnt = 0;
for (int i = 2; i <= n; i++) {
if (!isPrime[i]) {
primes[cnt++] = i;
}
for (int j = 0; j < cnt && i * primes[j] <= n; j++) {
isPrime[i * primes[j]] = true;
if (i % primes[j] == 0) {
break;
}
}
}
BigInteger num = BigInteger.valueOf(n);
if (!isPrime[n]) {
BigInteger phi = num.subtract(BigInteger.ONE);
for (int i = 0; i < cnt && primes[i] * primes[i] <= n; i++) {
if (n % primes[i] == 0) {
phi = phi.divide(BigInteger.valueOf(primes[i]));
phi = phi.multiply(BigInteger.valueOf(primes[i] - 1));
while (n % primes[i] == 0) {
n /= primes[i];
}
}
}
if (n > 1) {
phi = phi.divide(BigInteger.valueOf(n));
phi = phi.multiply(BigInteger.valueOf(n - 1));
}
return phi;
} else {
return num.subtract(BigInteger.valueOf(1));
}
}

public static void main(String[] args) {
BigInteger num = new BigInteger("12345678901234567890");
if (num.isProbablePrime(10)) {
System.out.println(num + " is prime.");
} else {
BigInteger phi = eulerSieve(num.intValue());
if (phi.gcd(num).equals(BigInteger.ONE)) {
System.out.println(num + " is prime.");
} else {
System.out.println(num + " is not prime.");
}
}
}
}

在main方法中，我们可以将要判断的数转化为BigInteger类型，然后使用isProbablePrime方法进行快速判断，如果不是质数，则使用欧拉筛来进一步判断。如果欧拉函数与该数的最大公约数为1，则该数为质数，否则不是。