首页 > 专题系列 > Java解POJ > POJ 3324 Lucas-Lehmer Test [解题报告] Java
2013
11-12

POJ 3324 Lucas-Lehmer Test [解题报告] Java

Lucas-Lehmer Test

问题描述 :

In mathematics, the Lucas-Lehmer test is a primality test for Mersenne numbers (numbers of the form 2n − 1). The test was originally developed by Edouard Lucas in 1856, and subsequently improved by Lucas in 1878 and Derrick Henry Lehmer in the 1930s. The well-known distributed computing project Great Internet Mersenne Prime Search (GIMPS) uses the test to locate Mersenne primes (Mersenne numbers that are also prime numbers). As of the time when this problem is composed, the largest known Mersenne prime is 232,382,657 − 1, which was discovered on September 4, 2006 by Curtis Cooper and Steven Boone.

The test works as follows. Let Mp = 2p − 1 be the Mersenne number to test with p a positive integer (in real applications only large primes are of interest since primality of Mp is easy to determine when p is relatively small and if p is composite, so is Mp). Define a sequence {si} for all i ≥ 0 by

s0 = 4;
si = s2i − 1 − 2 for all i > 0.

Then Mp is prime iff

sp − 2 ≡ 0 (mod Mp).

The number sp − 2 mod Mp is called the Lucas-Lehmer residue of p.

Your task is to write a simple implementation of the Lucas-Lehmer test.

输入:

The input contains one or more positive integers below 8,192 which are not necessarily primes, one on a each line. End-of-file (EOF) indicates the end of input.

输出:

For each integer in the input, output its Lucas-Lehmer residue in hexadecimal using digits 0 through 9 and lowercase letters a through f, each on a separate line.

样例输入:

59
61

样例输出:

64099e5fcbcaf36
0

解题代码:

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
import java.math.*;
public class Main 
{
 public static void main(String args[]) throws Exception {
	Scanner cin=new Scanner(System.in);
	BigInteger s,M;
	int p,i;
	while(cin.hasNext())
	{
		p=cin.nextInt();
		s=BigInteger.valueOf(4);
		M=BigInteger.ONE;
		M=M.shiftLeft(p).subtract(BigInteger.ONE);
		for(i=0;i< p-2;++i)
		{
			s=s.multiply(s).subtract(BigInteger.valueOf(2));
			while(s.bitLength()>p)
			{
				s=s.shiftRight(p).add(s.and(M));
			}
		}
		if(s.compareTo(BigInteger.ZERO)==0||s.compareTo(M)==0)
		{
			System.out.println(0);
			continue;
		}
		String ans="";
		while(s.compareTo(BigInteger.ZERO)>0)
		{
			long buf=s.mod(BigInteger.valueOf(16)).longValue();
			ans+=Integer.toHexString((int)buf);
			s=s.divide(BigInteger.valueOf(16));
		}
		for(i=ans.length()-1;i>=0;--i)System.out.print(ans.charAt(i));
		System.out.println();
	}
  }
}