A Cunningham chain is a sequence of prime numbers. It is of 2 types:
- Cunningham chain of the first kind: It is a sequence of prime numbers of length n described as below :
Let p1, p2, p3, …., pn be a cunningham chain of length n than
p2 = 2*p1 + 1
p3 = 4*p1 + 3
p4 = 8*p1 + 7
. . .
. . .
pn = 2n-1*p1 + (2n-1 – 1)
- Here p1, p2, p3, …., pn are all prime numbers. If any value of p comes out to be non-prime then chain ends at the number which came before it.
for p0 = 2, the sequence will be 2 5 11 23 47
Below is the implementation of the above:
C++
// C++ program for cunningham chain// Function to print the series// of first kind#include <bits/stdc++.h>using namespace std;// Function to print// Cunningham chain of the first kindvoid print(int p0){ int p1, i = 0, x, flag, k; // Iterate till all elements // are printed while (1) { flag = 1; x = (int)(pow(2, i)); p1 = x * p0 + (x - 1); // check prime or not for (k = 2; k < p1; k++) { if (p1 % k == 0) { flag = 0; break; } } if (flag == 0) break; printf("%d ", p1); i++; }}// Driver Codeint main(){ int p0 = 2; print(p0); return 0;} |
Java
// Java Program to print the // series of first kindclass GFG{// Function to print// Cunningham chain// of the first kindstatic void print(int p0){ int p1, i = 0, x, flag, k; // Iterate till all // elements are printed while (true) { flag = 1; x = (int)(Math.pow(2, i)); p1 = x * p0 + (x - 1); // check prime or not for (k = 2; k < p1; k++) { if (p1 % k == 0) { flag = 0; break; } } if (flag == 0) break; System.out.print(" " + p1); i++; }}// Driver Codepublic static void main(String args[]){ int p0 = 2; print(p0);}}// This code is contributed// by Kirti_Mangal |
Python3
# Python3 program for cunningham chain # Function to print Cunningham chain # of the first kind def print_C(p0): i = 0; # Iterate till all elements # are printed while(True): flag = 1; x = pow(2, i); p1 = x * p0 + (x - 1); # check prime or not for k in range(2, p1): if (p1 % k == 0): flag = 0; break; if (flag == 0): break; print(p1, end = " "); i += 1; # Driver Code p0 = 2; print_C(p0); # This code is contributed by mits |
C#
// C# Program to print the // series of first kindusing System;class GFG{// Function to print// Cunningham chain// of the first kindstatic void print(int p0){ int p1, i = 0, x, flag, k; // Iterate till all // elements are printed while (true) { flag = 1; x = (int)(Math.Pow(2, i)); p1 = x * p0 + (x - 1); // check prime or not for (k = 2; k < p1; k++) { if (p1 % k == 0) { flag = 0; break; } } if (flag == 0) break; Console.Write(" " + p1); i++; }}// Driver Codepublic static void Main(){ int p0 = 2; print(p0);}}// This code is contributed// by Akanksha Rai(Abby_akku) |
PHP
<?php// PHP program for cunningham chain// Function to print// Cunningham chain of the first kindfunction print_C($p0){ $p1 = 0; $i = 0; $x; $flag; $k; // Iterate till all elements // are printed while (1) { $flag = 1; $x = pow(2, $i); $p1 = $x * $p0 + ($x - 1); // check prime or not for ($k = 2; $k < $p1; $k++) { if ($p1 % $k == 0) { $flag = 0; break; } } if ($flag == 0) break; echo $p1 . " "; $i++; }}// Driver Code$p0 = 2;print_C($p0);// This code is contributed // by Akanksha Rai(Abby_akku) |
Javascript
<script>// Javascript program for cunningham chain// Function to print// Cunningham chain of the first kindfunction print_C(p0){ let p1 = 0; let i = 0; let x; let flag; let k; // Iterate till all elements // are printed while (1) { flag = 1; x = Math.pow(2, i); p1 = x * p0 + (x - 1); // check prime or not for (let k = 2; k < p1; k++) { if (p1 % k == 0) { flag = 0; break; } } if (flag == 0) break; document.write(p1 + " "); i++; }}// Driver Codelet p0 = 2;print_C(p0);// This code is contributed // by gfgking</script> |
Output:
2 5 11 23 47
- Cunningham chain of the second kind: It is a sequence of prime numbers of length n described as below:
Let p1, p2, p3, …., pn be a cunningham chain of length n than
p2 = 2*p1 – 1
p3 = 4*p1 – 3
p4 = 8*p1 – 7
. . .
. . .
pn = 2n-1*p1 – (2n-1 – 1)
- for p0 = 19, the sequence will be 19, 37, 73.
Below is the implementation of the above:
C++
// C++ program for cunningham chain// Function to print the series// of second kind#include <bits/stdc++.h>using namespace std;// Function to print// Cunningham chain of the second kindvoid print(int p0){ int p1, i = 0, x, flag, k; // Iterate till all elements // are printed while (1) { flag = 1; x = (int)(pow(2, i)); p1 = x * p0 - (x - 1); // check prime or not for (k = 2; k < p1; k++) { if (p1 % k == 0) { flag = 0; break; } } if (flag == 0) break; printf("%d ", p1); i++; }}// Driver Codeint main(){ int p0 = 19; print(p0); return 0;} |
Java
// Java program for cunningham chain // Function to print the series // of second kind class GFG{ // Function to print Cunningham chain// of the second kind static void print(int p0) { int p1, i = 0, x, flag, k; // Iterate till all elements // are printed while (true) { flag = 1; x = (int)(Math.pow(2, i)); p1 = x * p0 - (x - 1); // check prime or not for (k = 2; k < p1; k++) { if (p1 % k == 0) { flag = 0; break; } } if (flag == 0) break; System.out.print(p1+" "); i++; } } // Driver Code public static void main(String[] args) { int p0 = 19; print(p0); } }// This code is contributed by mits |
Python3
# Python3 program for cunningham chain # Function to print Cunningham chain# of the second kind def print_t(p0): i = 0; # Iterate till all elements # are printed while (True): flag = 1; x = pow(2, i); p1 = x * p0 - (x - 1); # check prime or not for k in range(2, p1): if (p1 % k == 0): flag = 0; break; if (flag == 0): break; print(p1,end=" "); i+=1; # Driver Code p0 = 19; print_t(p0); # This code is contributed by mits |
C#
// C# program for cunningham chain // Function to print the series // of second kind using System;class GFG{ // Function to print // Cunningham chain of the second kind static void print(int p0) { int p1, i = 0, x, flag, k; // Iterate till all elements // are printed while (true) { flag = 1; x = (int)(Math.Pow(2, i)); p1 = x * p0 - (x - 1); // check prime or not for (k = 2; k < p1; k++) { if (p1 % k == 0) { flag = 0; break; } } if (flag == 0) break; Console.Write(p1 + " "); i++; } } // Driver Code static void Main() { int p0 = 19; print(p0); } }// This code is contributed by mits |
PHP
<?php// PHP program for cunningham chain// Function to print// Cunningham chain of the second kindfunction print_t($p0){ $p1; $i = 0; $x; $flag; $k; // Iterate till all elements // are printed while (1) { $flag = 1; $x = pow(2, $i); $p1 = $x * $p0 - ($x - 1); // check prime or not for ($k = 2; $k < $p1; $k++) { if ($p1 % $k == 0) { $flag = 0; break; } } if ($flag == 0) break; echo $p1 . " "; $i++; }}// Driver Code$p0 = 19;print_t($p0);// This code is contributed// by Akanksha Rai(Abby_akku) |
Javascript
<script>// JavaScript program for cunningham chain// Function to print// Cunningham chain of the second kindfunction print(p0){ var p1, i = 0, x, flag = 1, k, m = 4; // Iterate till all elements // are printed while (flag) { flag = 1; x = Math.pow(2, i); p1 = x * p0 - (x - 1); // check prime or not for (k = 2; k < p1; k++) { if (p1 % k == 0) { flag = 0; break; } } if (flag == 0) break; document.write(p1 + " "); i++; }}// Driver Codevar p0 = 19;print(p0);//This code is contributed by Shivani</script> |
Output:
19 37 73
Time complexity : O(n^2), where n is the number of elements in the Cunningham chain of the first kind.
Space complexity: O(1), as it only uses a few variables and doesn’t increase with the size of the input.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!