### Large non-Mersenne prime题号：97 难度： 5 中英对照

The first known prime found to exceed one million digits was discovered in 1999, and is a Mersenne prime of the form 26972593−1; it contains exactly 2,098,960 digits. Subsequently other Mersenne primes, of the form 2p−1, have been found which contain more digits.

However, in 2004 there was found a massive non-Mersenne prime which contains 2,357,207 digits: 28433×27830457+1.

Find the last ten digits of this prime number.

### Code

public final class p97 {
private static final int MAX_N=50;
public static void main(String[] args){
long start=System.nanoTime();
long result = run();
long end=System.nanoTime();
System.out.println(result);
System.out.println( (end-start)/1000000 + "ms" );
}
public static long run(){
BigInteger modulus = BigInteger.TEN.pow(10);	//modulus=10^10
BigInteger n = BigInteger.valueOf(2).modPow(BigInteger.valueOf(7830457), modulus); //n=（2^7830457）mod（10^10）
n = n.multiply(BigInteger.valueOf(28433)).mod(modulus);// n=(n*28433)mod(10^10)
n = n.add(BigInteger.ONE).mod(modulus);// n=(n+1)mod(10^10)
return n.longValue();	//将BigInteger转成long类型
}

}
8739992577
2ms