Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Lucas-Lehmer Test
Description In mathematics, the Lucas-Lehmer test is a primality test for Mersenne numbers (numbers of the form 2 ^{32,382,657} − 1, which was discovered on September 4, 2006 by Curtis Cooper and Steven Boone.The test works as follows. Let − 1 be the Mersenne number to test with ^{p}p a positive integer (in real applications only large primes are of interest since primality of M is easy to determine when _{p}p is relatively small and if p is composite, so is M). Define a sequence {_{p}s} for all _{i}i ≥ 0 by
Then
The number _{ − 2} mod M is called the _{p}Lucas-Lehmer residue of p.Your task is to write a simple implementation of the Lucas-Lehmer test. Input The input contains one or more positive integers below 8,192 which are Output For each integer in the input, output its Lucas-Lehmer residue in hexadecimal using digits Sample Input 59 61 Sample Output 64099e5fcbcaf36 0 Source POJ Monthly--2007.08.05, frkstyc |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator