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 Nth 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 countth 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 notint prime[100001];// Sieve of Eratosthenes to // generate all possible primesvoid 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 Seriesvoid 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 Codeint32_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 approachimport 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 primesstatic 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 Seriesstatic 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 codepublic 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 notprime = [True for i in range(100001)]# Sieve of Eratosthenes to # generate all possible primesdef 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 Seriesdef 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 Codeif __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 codestatic 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(N2 + log(log(maxm))), where it takes O(N2) 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
