# Primality Test | Set 5(Using Lucas-Lehmer Series)

In this article we will discuss about Lucas-Lehmer series which is used to check primality of prime numbers of the form 2p – 1 where p is an integer.

First let’s see what is Lucas-Lehmer series.

The Lucas-Lehmer series can be expressed as : Hence the series is:
Term 0: 4,
Term 1: 4*4 – 2 = 14,
Term 2: 14*14 – 2 = 194,
Term 3: 194*194 – 2 = 37634,
Term 4: 37634*37634 – 2 = 1416317954, … and so on.

Below is the program to find out first n terms of the Lucas-Lehmer series.

## C++

 `// C++ program to find out Lucas-Lehmer series. ` `#include ` `#include ` `using` `namespace` `std; ` ` `  `// Function to find out first n terms ` `// (considering 4 as 0th term) of ` `// Lucas-Lehmer series. ` `void` `LucasLehmer(``int` `n) { ` ` `  `  ``// the 0th term of the series is 4. ` `  ``unsigned ``long` `long` `current_val = 4; ` ` `  `  ``// create an array to store the terms. ` `  ``vector series; ` ` `  `  ``// compute each term and add it to the array. ` `  ``series.push_back(current_val); ` `  ``for` `(``int` `i = 0; i < n; i++) { ` `    ``current_val = current_val * current_val - 2; ` `    ``series.push_back(current_val); ` `  ``} ` ` `  `  ``// print out the terms one by one. ` `  ``for` `(``int` `i = 0; i <= n; i++)  ` `    ``cout << ``"Term "` `<< i << ``": "` `        ``<< series[i] << endl;   ` `} ` ` `  `// Driver program ` `int` `main() { ` `  ``int` `n = 5; ` `  ``LucasLehmer(n); ` `  ``return` `0; ` `} `

/div>

## Java

 `// Java program to find out ` `// Lucas-Lehmer series. ` `import` `java.util.*; ` ` `  `class` `GFG  ` `{ ` ` `  `    ``// Function to find out  ` `    ``// first n terms(considering  ` `    ``// 4 as 0th term) of Lucas- ` `    ``// Lehmer series. ` `    ``static` `void` `LucasLehmer(``int` `n)  ` `    ``{ ` ` `  `        ``// the 0th term of ` `        ``// the series is 4. ` `        ``long` `current_val = ``4``; ` ` `  `        ``// create an array ` `        ``// to store the terms. ` `        ``ArrayList series = ``new` `ArrayList<>(); ` ` `  `         ``// compute each term  ` `        ``// and add it to the array. ` `        ``series.add(current_val); ` `        ``for` `(``int` `i = ``0``; i < n; i++)  ` `        ``{ ` `            ``current_val = current_val ` `                    ``* current_val - ``2``; ` `            ``series.add(current_val); ` `        ``} ` ` `  `        ``// print out the ` `       ``// terms one by one. ` `        ``for` `(``int` `i = ``0``; i <= n; i++)  ` `        ``{ ` `            ``System.out.println(``"Term "` `+ i ` `                    ``+ ``": "` `+ series.get(i)); ` `        ``} ` `    ``} ` ` `  `    ``// Driver Code ` `    ``public` `static` `void` `main(String[] args)  ` `    ``{ ` ` `  `        ``int` `n = ``5``; ` `        ``LucasLehmer(n); ` `    ``} ` `} ` ` `  `// This code has been contributed by 29AjayKumar `

## C#

 `// C# program to find out ` `// Lucas-Lehmer series. ` `using` `System; ` `using` `System.Collections.Generic; ` ` `  `class` `GFG ` `{ ` `     `  `// Function to find out  ` `// first n terms(considering  ` `// 4 as 0th term) of Lucas- ` `// Lehmer series. ` `static` `void` `LucasLehmer(``int` `n)  ` `{ ` ` `  `// the 0th term of ` `// the series is 4. ` `long` `current_val = 4; ` ` `  `// create an array ` `// to store the terms. ` `List<``long``> series = ``new` `List<``long``>(); ` ` `  `// compute each term  ` `// and add it to the array. ` `series.Add(current_val); ` `for` `(``int` `i = 0; i < n; i++) ` `{ ` `    ``current_val = current_val *  ` `                  ``current_val - 2; ` `    ``series.Add(current_val); ` `} ` ` `  `// print out the ` `// terms one by one. ` `for` `(``int` `i = 0; i <= n; i++)  ` `    ``Console.WriteLine(``"Term "` `+ i +  ` `                      ``": "` `+ series[i]);  ` `} ` ` `  `// Driver Code ` `static` `void` `Main() ` `{ ` `    ``int` `n = 5; ` `    ``LucasLehmer(n); ` `} ` `} ` ` `  `// This code is contributed by  ` `// ManishShaw(manishshaw1) `

Output:

```Term 0: 4
Term 1: 14
Term 2: 194
Term 3: 37634
Term 4: 1416317954
Term 5: 2005956546822746114
```

We can use string to store the big numbers of the series.

Now what is the relation with prime numbers of this Lucas-Lehmer series?

1. First thing is that we can only check the primality of those numbers which we can represent as, x = (2p – 1) where p is an integer.
2. Now we have to find out the (p-1)th term of Lucas-Lehmer series.
3. If this term is a multiple of x, then x is a prime number.
4. When x is large, i.e. p is large then we may find difficulties to find out the (p-1)th term of the series.

Rather what we can do:
1. Start calculating Lucas-Lehmer series from 0th term and rather storing the whole term only store the s[i]%x (i.e. term modulo x).
2. Compute the next number of this modified series using the previous term. s[i] = (s[i-1]2 – 2)%x.
3. Compute up to (p-1)th term.
4. If the (p-1)th term is 0 then x is prime, otherwise not. Hence, s[p-1] has to be 0 to be x = (2p – 1) prime.

Examples:

```Is 2^7 - 1 = 127 is a prime?
so here x = 127, p = 7-1 = 6.
Hence the modified Lucas-Lehmer series is:
term 1: 4,
term 2: (4*4 - 2) % 127 = 14,
term 3: (14*14 - 2) % 127 = 67,
term 4: (67*67 - 2) % 127 = 42,
term 5: (42*42 - 2) % 127 = 111,
term 6: (111*111) % 127 = 0.
Here the 6th term is 0 so 127 is a prime number.
```

Code to check whether 2^p-1 is prime or not

## C++

 `// CPP program to check for primality using ` `// Lucas-Lehmer series. ` `#include ` `#include ` `using` `namespace` `std; ` ` `  `// Function to check whether (2^p - 1) ` `// is prime or not. ` `bool` `isPrime(``int` `p) { ` ` `  `  ``// generate the number ` `  ``long` `long` `checkNumber = ``pow``(2, p) - 1; ` ` `  `  ``// First number of the series ` `  ``long` `long` `nextval = 4 % checkNumber; ` ` `  `  ``// Generate the rest (p-2) terms ` `  ``// of the series. ` `  ``for` `(``int` `i = 1; i < p - 1; i++)  ` `    ``nextval = (nextval * nextval - 2) % checkNumber;   ` ` `  `  ``// now if the (p-1)th term is ` `  ``// 0 return true else false. ` `  ``return` `(nextval == 0); ` `} ` ` `  `// Driver Program ` `int` `main() { ` `  ``// Check whether 2^p-1 is prime or not. ` `  ``int` `p = 7; ` ` `  `  ``long` `long` `checkNumber = ``pow``(2, p) - 1; ` ` `  `  ``if` `(isPrime(p)) ` `    ``cout << checkNumber << ``" is Prime."``; ` `  ``else` `    ``cout << checkNumber << ``" is not Prime."``; ` ` `  `  ``return` `0; ` `} `

## Java

 `// Java program to check for primality using ` `// Lucas-Lehmer series. ` ` `  `class` `GFG{ ` `// Function to check whether (2^p - 1) ` `// is prime or not. ` `static` `boolean` `isPrime(``int` `p) { ` ` `  `// generate the number ` `double` `checkNumber = Math.pow(``2``, p) - ``1``; ` ` `  `// First number of the series ` `double` `nextval = ``4` `% checkNumber; ` ` `  `// Generate the rest (p-2) terms ` `// of the series. ` `for` `(``int` `i = ``1``; i < p - ``1``; i++)  ` `    ``nextval = (nextval * nextval - ``2``) % checkNumber;  ` ` `  `// now if the (p-1)th term is ` `// 0 return true else false. ` `return` `(nextval == ``0``); ` `} ` ` `  `// Driver Program ` `public` `static` `void` `main(String[] args) { ` `// Check whether 2^p-1 is prime or not. ` `int` `p = ``7``; ` `double` `checkNumber = Math.pow(``2``, p) - ``1``; ` ` `  `if` `(isPrime(p)) ` `    ``System.out.println((``int``)checkNumber+``" is Prime."``); ` `else` `    ``System.out.println((``int``)checkNumber+``" is not Prime."``); ` ` `  `} ` `} ` `// This code is contributed by mits `

## Python3

 `# Python3 Program to check for primality  ` `# using Lucas-Lehmer series. ` ` `  `# Function to check whether (2^p - 1) ` `# is prime or not. ` `def` `isPrime(p): ` ` `  `    ``# generate the number ` `    ``checkNumber ``=` `2` `*``*` `p ``-` `1` ` `  `    ``# First number of the series ` `    ``nextval ``=` `4` `%` `checkNumber ` ` `  `    ``# Generate the rest (p-2) terms ` `    ``# of the series ` `    ``for` `i ``in` `range``(``1``, p ``-` `1``): ` `        ``nextval ``=` `(nextval ``*` `nextval ``-` `2``) ``%` `checkNumber ` ` `  `    ``# now if the (p-1) the term is ` `    ``# 0 return true else false. ` `    ``if` `(nextval ``=``=` `0``): ``return` `True` `    ``else``: ``return` `False` ` `  `# Driver Code ` ` `  `# Check whetherr 2^(p-1) ` `# is prime or not. ` `p ``=` `7` `checkNumber ``=` `2` `*``*` `p ``-` `1` ` `  `if` `isPrime(p): ` `    ``print``(checkNumber, ``'is Prime.'``) ` `else``: ` `    ``print``(checkNumber, ``'is not Prime'``) ` ` `  `# This code is contributed by egoista. `

## C#

 `// C# program to check for primality using ` `// Lucas-Lehmer series. ` `using` `System; ` ` `  `class` `GFG{ ` `// Function to check whether (2^p - 1) ` `// is prime or not. ` `static` `bool` `isPrime(``int` `p) { ` ` `  `// generate the number ` `double` `checkNumber = Math.Pow(2, p) - 1; ` ` `  `// First number of the series ` `double` `nextval = 4 % checkNumber; ` ` `  `// Generate the rest (p-2) terms ` `// of the series. ` `for` `(``int` `i = 1; i < p - 1; i++)  ` `    ``nextval = (nextval * nextval - 2) % checkNumber;  ` ` `  `// now if the (p-1)th term is ` `// 0 return true else false. ` `return` `(nextval == 0); ` `} ` ` `  `// Driver Program ` `static` `void` `Main() { ` `// Check whether 2^p-1 is prime or not. ` `int` `p = 7; ` `double` `checkNumber = Math.Pow(2, p) - 1; ` ` `  `if` `(isPrime(p)) ` `    ``Console.WriteLine((``int``)checkNumber+``" is Prime."``); ` `else` `    ``Console.WriteLine((``int``)checkNumber+``" is not Prime."``); ` ` `  `} ` `} ` `// This code is contributed by mits `

## PHP

 ` `

Output:

```127 is Prime.
```

The largest prime number at the time of writing this article is (2^(77232917) – 1) (discovered 2017-12-26). It has 23, 249, 425 digits. This prime numbers are found in the same way discussed above. Huge computational power and several months of processing is required to find out this kind of large prime numbers.
Interesting fact is that for checking this much big prime numbers, p are also taken prime. After processing if it finds that the number x is not prime then p is taken as the next prime number and the same process is run.