Nth Term of a Fibonacci Series of Primes formed by concatenating pairs of Primes in a given range

0 0 10 minutes read

Given two integers X and Y, the task is to perform the following operations:

Find all prime numbers in the range [X, Y].
Generate all numbers possible by combining every pair of primes in the given range.
Find the prime numbers among all the possible numbers generated above. Calculate the count of primes among them, say N.
Print the N^th term of a Fibonacci Series formed by having the smallest and largest primes from the above list as the first two terms of the series.

Examples:

Input: X = 2 Y = 40
Output: 13158006689
Explanation:
All primes in the range [X, Y] = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]

All possible numbers generated by concatenating each pair of prime = [23, 25, 27, 211, 213, 217, 219, 223, 229, 231, 32, 35, 37, 311, 313, 319, 323, 329, 331, 337, 52, 53, 57, 511, 513, 517, 519, 523, 529, 531, 537, 72, 73, 75, 711, 713, 717, 719, 723, 729, 731, 737, 112, 113, 115, 117, 1113, 1117, 1119, 1123, 1129, 1131, 1137, 132, 133, 135, 137, 1311, 1317, 1319, 1323, 1329, 1331, 1337, 172, 173, 175, 177, 1711, 1713, 1719, 1723, 1729, 1731, 1737, 192, 193, 195, 197, 1911, 1913, 1917, 1923, 1929, 1931, 1937, 232, 233, 235, 237, 2311, 2313, 2317, 2319, 2329, 2331, 2337, 292, 293, 295, 297, 2911, 2913, 2917, 2919, 2923, 2931, 2937, 312, 315, 317, 3111, 3113, 3117, 3119, 3123, 3129, 3137, 372, 373, 375, 377, 3711, 3713, 3717, 3719, 3723, 3729, 3731]

All primes among the generated numbers=[193, 3137, 197, 2311, 3719, 73, 137, 331, 523, 1931, 719, 337, 211, 23, 1117, 223, 1123, 229, 37, 293, 2917, 1319, 1129, 233, 173, 3119, 113, 53, 373, 311, 313, 1913, 1723, 317]
Count of the primes = 34
Smallest Prime = 23
Largest Prime = 3719
Therefore, the 34th term of the Fibonacci series, having 23 and 3719 as the first two terms, is 13158006689.

Input: X = 1, Y = 10
Output: 1053

Approach:
Follow the steps below to solve the problem:

Generate all possible primes using the Sieve of Eratosthenes.
Traverse the range [X, Y] and generate all primes in the range with the help of primes[] array generated in the step above.
Traverse the list of primes and generate all possible pairs from the list.
For each pair, concatenate the two primes and check if their concatenation is a prime or not.
Find the maximum and minimum of all such primes and count all such primes obtained.
Finally, print the count^th of a Fibonacci series having minimum and maximum obtained in the above step as the first two terms of the series.

Below is the implementation of the above approach:

C++

// C++ program to implement
// the above approach
#include<bits/stdc++.h>
using namespace std;
#define int long long int
 
// Stores at each index if it's a 
// prime or not
int prime[100001];
 
// Sieve of Eratosthenes to 
// generate all possible primes
void SieveOfEratosthenes()
{
    for(int i = 0; i < 100001; i++)
        prime[i] = 1;
         
    int p = 2;
    while (p * p <= 100000)
    {
         
        // If p is a prime
        if (prime[p] == 1)
        {
             
            // Set all multiples of
            // p as non-prime
            for(int i = p * p; 
                    i < 100001; 
                    i += p)
                prime[i] = 0;
        }     
        p += 1;
    }     
}
     
int join(int a, int b)
{
    int mul = 1;
    int bb = b;
     
    while(b != 0)
    {
        mul *= 10;
        b /= 10;
    }
    a *= mul;
    a += bb;
    return a;
}
 
// Function to generate the 
// required Fibonacci Series
void fibonacciOfPrime(int n1, int n2)
{
    SieveOfEratosthenes();
     
    // Stores all primes between
    // n1 and n2
    vector<int>initial;
     
    // Generate all primes between
    // n1 and n2
    for(int i = n1; i <= n2; i++)
        if (prime[i])
            initial.push_back(i);
             
    // Stores all concatenations
    // of each pair of primes
    vector<int>now;
     
    // Generate all concatenations
    // of each pair of primes
    for(auto a:initial)
        for(auto b:initial)
            if (a != b)
            {
                int c = join(a,b);
                now.push_back(c);
            }
                 
                 
    // Stores the primes out of the
    // numbers generated above
    vector<int>current;
     
    for(auto x:now)
        if (prime[x])
            current.push_back(x);
             
    // Store the unique primes
    set<int>current_set;
    for(auto i:current)
        current_set.insert(i);
     
    // Find the minimum
    int first = *min_element(current_set.begin(),
                             current_set.end());
     
    // Find the minimum
    int second = *max_element(current_set.begin(),
                              current_set.end());
                               
    // Find N
    int count = current_set.size() - 1;
    int curr = 1;
    int c;
     
    while( curr < count)
    {
        c = first + second;
        first = second;
        second = c;
        curr += 1;
    }
     
    // Print the N-th term
    // of the Fibonacci Series
    cout << (c) << endl;
}
     
// Driver Code
int32_t main()
{
    int x = 2;
    int y = 40;
     
    fibonacciOfPrime(x, y);
}
 
// This code is contributed by Stream_Cipher

Java

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{ 
 
// Stores at each index if it's a  
// prime or not     
static int prime[] = new int [100001];
 
// Sieve of Eratosthenes to 
// generate all possible primes
static void SieveOfEratosthenes()
{
    for(int i = 0; i < 100001; i++)
        prime[i] = 1;
         
    int p = 2;
    while (p * p <= 100000)
    {
         
        // If p is a prime
        if (prime[p] == 1)
        {
             
            // Set all multiples of
            // p as non-prime
            for(int i = p * p;
                    i < 100001;
                    i += p)
                prime[i] = 0;
        }     
        p += 1;
    }     
}
 
static int join(int a,int b)
{
    int mul = 1;
    int bb = b;
     
    while(b != 0)
    {
        mul *= 10;
        b /= 10;
    }
    a *= mul;
    a += bb;
    return a;
}
 
// Function to generate the 
// required Fibonacci Series
static void fibonacciOfPrime(int n1, int n2)
{
    SieveOfEratosthenes();
     
    // Stores all primes between
    // n1 and n2
    Vector<Integer> initial = new Vector<>();
     
    // Generate all primes between
    // n1 and n2
    for(int i = n1; i <= n2; i++)
        if (prime[i] == 1)
            initial.add(i);
             
    // Stores all concatenations
    // of each pair of primes
    Vector<Integer> now = new Vector<>();
     
    // Generate all concatenations
    // of each pair of primes
    for(int i = 0; i < initial.size(); i++)
    {
        for(int j = 0; j < initial.size(); j++)
        {
            int a = (int)initial.get(i);
            int b = (int)initial.get(j);
             
            if (a != b)
            {
                int c = join(a, b);
                now.add(c);
            }
        }
    }
     
    // Stores the primes out of the
    // numbers generated above
    Vector<Integer> current = new Vector<>();
     
    for(int i = 0; i < now.size(); i++)
        if (prime[(int)now.get(i)] == 1)
            current.add((int)now.get(i));
             
    // Store the unique primes
    int cnt[] = new int[1000009];
    for(int i = 0; i < 1000001; i++)
        cnt[i] = 0;
         
    Vector<Integer> current_set = new Vector<>();
    for(int i = 0; i < current.size(); i++)
    {
        cnt[(int)current.get(i)]++;
        if (cnt[(int)current.get(i)] == 1)
            current_set.add((int)current.get(i));
    }
     
    // Find the minimum
    long first = 1000000000;
    for(int i = 0; i < current_set.size(); i++)
        first = Math.min(first, 
                         (int)current_set.get(i));
                          
    // Find the minimum
    long second = 0;
    for(int i = 0; i < current_set.size(); i++)
        second = Math.max(second,
                         (int)current_set.get(i));
                          
    // Find N
    int count = current_set.size() - 1;
    long curr = 1;
    long c = 0;
     
    while(curr < count)
    {
        c = first + second;
        first = second;
        second = c;
        curr += 1;
    }
     
    // Print the N-th term
    // of the Fibonacci Series
    System.out.println(c);
}
 
// Driver code
public static void main(String[] args) 
{ 
    int x = 2;
    int y = 40;
     
    fibonacciOfPrime(x, y);
} 
}
 
// This code is contributed by Stream_Cipher

Python3

# Python3 Program to implement
# the above approach
 
# Stores at each index if it's a 
# prime or not
prime = [True for i in range(100001)]
 
# Sieve of Eratosthenes to 
# generate all possible primes
def SieveOfEratosthenes(): 
     
    p = 2
    while (p * p <= 100000):
         
        # If p is a prime
        if (prime[p] == True):
             
            # Set all multiples of p as non-prime
            for i in range(p * p, 100001, p):
                prime[i] = False
                 
        p += 1
 
# Function to generate the 
# required Fibonacci Series
def fibonacciOfPrime(n1, n2):
     
    SieveOfEratosthenes()
     
    # Stores all primes between
    # n1 and n2
    initial = []
     
    # Generate all primes between
    # n1 and n2
    for i in range(n1, n2):
        if prime[i]:
            initial.append(i)
             
    # Stores all concatenations
    # of each pair of primes
    now = []
     
    # Generate all concatenations
    # of each pair of primes
    for a in initial:
        for b in initial:
            if a != b:
                c = str(a) + str(b)
                now.append(int(c))
                 
    # Stores the primes out of the
    # numbers generated above
    current = []
     
    for x in now:
        if prime[x]:
            current.append(x)
             
    # Store the unique primes
    current = set(current)
     
    # Find the minimum
    first = min(current)
     
    # Find the minimum
    second = max(current)
     
    # Find N
    count = len(current) - 1
    curr = 1
     
    while curr < count:
        c = first + second
        first = second
        second = c
        curr += 1
     
    # Print the N-th term
    # of the Fibonacci Series
    print(c)
 
# Driver Code
if __name__ == "__main__":
 
    x = 2
    y = 40
    fibonacciOfPrime(x, y)

C#

// C# program to implement 
// the above approach 
using System;
using System.Collections.Generic; 
class GFG{
     
// Stores at each index if it's a   
// prime or not      
static int[] prime = new int[100001]; 
       
// Sieve of Eratosthenes to  
// generate all possible primes 
static void SieveOfEratosthenes() 
{ 
  for(int i = 0; i < 100001; i++) 
    prime[i] = 1; 
 
  int p = 2; 
  while (p * p <= 100000) 
  { 
    // If p is a prime 
    if (prime[p] == 1) 
    { 
      // Set all multiples of 
      // p as non-prime 
      for(int i = p * p; 
              i < 100001; i += p) 
        prime[i] = 0; 
    } 
     
    p += 1; 
  }      
} 
       
static int join(int a,
                int b) 
{ 
  int mul = 1; 
  int bb = b; 
 
  while(b != 0) 
  { 
    mul *= 10; 
    b /= 10; 
  } 
   
  a *= mul; 
  a += bb; 
  return a; 
} 
       
// Function to generate the  
// required Fibonacci Series 
static void fibonacciOfPrime(int n1, 
                             int n2) 
{ 
  SieveOfEratosthenes(); 
 
  // Stores all primes 
  // between n1 and n2 
  List<int> initial = 
            new List<int>(); 
 
  // Generate all primes 
  // between n1 and n2 
  for(int i = n1; i <= n2; i++) 
    if (prime[i] == 1) 
      initial.Add(i); 
 
  // Stores all concatenations 
  // of each pair of primes 
  List<int> now = 
            new List<int>(); 
 
  // Generate all concatenations 
  // of each pair of primes 
  for(int i = 0; i < initial.Count; i++) 
  { 
    for(int j = 0; j < initial.Count; j++) 
    { 
      int a = initial[i]; 
      int b = initial[j]; 
 
      if (a != b) 
      { 
        int C = join(a, b); 
        now.Add(C); 
      } 
    } 
  } 
 
  // Stores the primes out of the 
  // numbers generated above 
  List<int> current = 
            new List<int>(); 
 
  for(int i = 0; i < now.Count; i++) 
    if (prime[now[i]] == 1) 
      current.Add(now[i]); 
 
  // Store the unique primes 
  int[] cnt = new int[1000009]; 
   
  for(int i = 0; i < 1000001; i++) 
    cnt[i] = 0; 
 
  List<int> current_set = 
            new List<int>(); 
   
  for(int i = 0; i < current.Count; i++) 
  { 
    cnt[current[i]]++; 
     
    if (cnt[current[i]] == 1) 
      current_set.Add(current[i]); 
  } 
 
  // Find the minimum 
  long first = 1000000000; 
   
  for(int i = 0; 
          i < current_set.Count; i++) 
    first = Math.Min(first, 
                     current_set[i]); 
 
  // Find the minimum 
  long second = 0; 
   
  for(int i = 0; 
          i < current_set.Count; i++) 
    second = Math.Max(second, 
                      current_set[i]); 
   
  // Find N 
  int count = current_set.Count - 1; 
  long curr = 1; 
  long c = 0; 
 
  while(curr < count) 
  { 
    c = first + second; 
    first = second; 
    second = c; 
    curr += 1; 
  } 
 
  // Print the N-th term 
  // of the Fibonacci Series 
  Console.WriteLine(c); 
} 
 
// Driver code
static void Main() 
{
  int x = 2; 
  int y = 40; 
  fibonacciOfPrime(x, y); 
}
}
 
// This code is contributed by divyeshrabadiya07

Javascript

<script>
    // Javascript program to implement the above approach
     
    // Stores at each index if it's a prime or not    
    let prime = new Array(100001);
 
    // Sieve of Eratosthenes to
    // generate all possible primes
    function SieveOfEratosthenes()
    {
        for(let i = 0; i < 100001; i++)
            prime[i] = 1;
 
        let p = 2;
        while (p * p <= 100000)
        {
 
            // If p is a prime
            if (prime[p] == 1)
            {
 
                // Set all multiples of
                // p as non-prime
                for(let i = p * p; i < 100001; i += p)
                    prime[i] = 0;
            }    
            p += 1;
        }    
    }
 
    function join(a, b)
    {
        let mul = 1;
        let bb = b;
 
        while(b != 0)
        {
            mul *= 10;
            b = parseInt(b / 10, 10);
        }
        a *= mul;
        a += bb;
        return a;
    }
 
    // Function to generate the
    // required Fibonacci Series
    function fibonacciOfPrime(n1, n2)
    {
        SieveOfEratosthenes();
 
        // Stores all primes between
        // n1 and n2
        let initial = [];
 
        // Generate all primes between
        // n1 and n2
        for(let i = n1; i <= n2; i++)
            if (prime[i] == 1)
                initial.push(i);
 
        // Stores all concatenations
        // of each pair of primes
        let now = [];
 
        // Generate all concatenations
        // of each pair of primes
        for(let i = 0; i < initial.length; i++)
        {
            for(let j = 0; j < initial.length; j++)
            {
                let a = initial[i];
                let b = initial[j];
 
                if (a != b)
                {
                    let c = join(a, b);
                    now.push(c);
                }
            }
        }
 
        // Stores the primes out of the
        // numbers generated above
        let current = [];
 
        for(let i = 0; i < now.length; i++)
            if (prime[now[i]] == 1)
                current.push(now[i]);
 
        // Store the unique primes
        let cnt = new Array(1000009);
        for(let i = 0; i < 1000001; i++)
            cnt[i] = 0;
 
        let current_set = [];
        for(let i = 0; i < current.length; i++)
        {
            cnt[current[i]]++;
            if (cnt[current[i]] == 1)
                current_set.push(current[i]);
        }
 
        // Find the minimum
        let first = 1000000000;
        for(let i = 0; i < current_set.length; i++)
            first = Math.min(first, current_set[i]);
 
        // Find the minimum
        let second = 0;
        for(let i = 0; i < current_set.length; i++)
            second = Math.max(second, current_set[i]);
 
        // Find N
        let count = current_set.length - 1;
        let curr = 1;
        let c = 0;
 
        while(curr < count)
        {
            c = first + second;
            first = second;
            second = c;
            curr += 1;
        }
 
        // Print the N-th term
        // of the Fibonacci Series
        document.write(c);
    }
     
    let x = 2;
    let y = 40;
      
    fibonacciOfPrime(x, y);
 
</script>

Output:

13158006689

Time Complexity: O(N² + log(log(maxm))), where it takes O(N²) to generate all pairs and O(1) to check if a number is prime or not and maxm is the size of prime[]
Auxiliary Space: O(maxm)

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 zambiatek!