当前位置:首页 » Project Euler » 详细页

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.

Solution

题目要求$$28433\times2^{7830457}+1$$的最后十位 用java.math.BigInteger类即可完成,函数的解释详见代码的注释 将数对10^10取余即可得到最后十位

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