Given a number N, the task is to find the primes within range [1, N] which is also a part of a Tribonacci series starting with {0, 0, 1}.
Note: A Tribonacci series is a series in which the next term is the sum of the previous three terms.
Examples:
Input: N = 10
Output: 2 7
Explanation: The first few terms are 0, 0, 1, 1, 2, 4, 7, 13.
Primes in the range [1, 10] are 2 and 7.Input: N = 2
Output: 2
Naive approach: The simplest approach is to generate a list of Tribonacci numbers in range [1, N] and find the prime numbers in the series which are in the range [1, N].
Time complexity: O(N * √N)
Auxiliary space: O(N)
Efficient Approach: This problem can be solved efficiently based on the following idea:
Generate a list of primes using Sieve of Eratosthenes and then generate Tribonacci number by formula t(n) = t(n-1)+t(n-2)+t(n-3) and find all the prime numbers of the series.
Follow the below steps to implement the above idea:
- Generate a list of primes using Sieve of Eratosthenes.
- Iterate from i = 3 to n (where nth Tribonacci number is at least N):
- Calculate the ith Tribonacci number by formula t(n) = t(n-1)+t(n-2)+t(n-3)
- Check if the t(n) is prime with the help of the already calculated prime numbers.
- Store them in an array (say answer[]).
- Finally print all the elements of the answer[].
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find the primes upto N using// Sieve of Eratosthenes techniquevoid sieve(vector<bool>& primes, int N){ for (int i = 2; i * i <= N; i++) { if (primes[i] == true) { for (int j = i + i; j <= N; j = j + i) { primes[j] = false; } } }}// Function to find the count of the numbersvector<int> findValues(int N){ // Stores all the prime number till n vector<bool> primes(N + 1, true); // 0 and 1 is not prime number primes[0] = false; primes[1] = false; sieve(primes, N); vector<int> tribonacci(N + 1); tribonacci[0] = 0; tribonacci[1] = 0; tribonacci[2] = 1; // Generating the sequence using formula // t(i) = t(i-1) + t(i-2) + t(i-3). for (int i = 3; tribonacci[i - 1] <= N; i++) { tribonacci[i] = tribonacci[i - 1] + tribonacci[i - 2] + tribonacci[i - 3]; } // Store the answer vector<int> ans; // Iterating over all the Tribonacci series for (int i = 0; tribonacci[i] <= N; i++) { int p = tribonacci[i]; // Check if the ith tribonacci // is prime or not if (primes[p] == true) { ans.push_back(p); } } return ans;}// Driver code.int main(){ int N = 10; // Function call vector<int> ans = findValues(N); // Printing Tribonacci numbers which are prime. for (int i = 0; i < ans.size(); i++) { cout << ans[i] << " "; } if (ans.size() == 0) cout << -1; return 0;} |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;class GFG { // Function to find the primes upto N using // Sieve of Eratosthenes technique public static void sieve(boolean primes[], int N) { for (int i = 2; i * i <= N; i++) { if (primes[i] == true) { for (int j = i + i; j <= N; j = j + i) { primes[j] = false; } } } } // Function to find the count of the numbers public static ArrayList<Integer> findValues(int N) { // Stores all the prime number till n boolean primes[] = new boolean[N + 1]; for (int i = 0; i < N + 1; i++) { primes[i] = true; } // 0 and 1 is not prime number primes[0] = false; primes[1] = false; sieve(primes, N); int tribonacci[] = new int[N + 1]; tribonacci[0] = 0; tribonacci[1] = 0; tribonacci[2] = 1; // Generating the sequence using formula // t(i) = t(i-1) + t(i-2) + t(i-3). for (int i = 3; tribonacci[i - 1] <= N; i++) { tribonacci[i] = tribonacci[i - 1] + tribonacci[i - 2] + tribonacci[i - 3]; } // Store the answer ArrayList<Integer> ans = new ArrayList<>(); // Iterating over all the Tribonacci series for (int i = 0; tribonacci[i] <= N; i++) { int p = tribonacci[i]; // Check if the ith tribonacci // is prime or not if (primes[p] == true) { ans.add(p); } } return ans; } // Driver Code public static void main(String[] args) { int N = 10; // Function call ArrayList<Integer> ans = findValues(N); // Printing Tribonacci numbers which are prime. for (int i = 0; i < ans.size(); i++) { System.out.print(ans.get(i) + " "); } if (ans.size() == 0) System.out.print(-1); }}// This code is contributed by Rohit Pradhan |
Python3
# Python code to implement the approach# Function to find the primes upto N using# Sieve of Eratosthenes techniquedef sieve(primes, N): i = 2 while(i * i <= N): if (primes[i] == True): for j in range(i + i, N+1, i): primes[j] = False i += 1# Function to find the count of the numbersdef findValues(N): # Stores all the prime number till n primes = [True for i in range(N + 1)] # 0 and 1 is not prime number primes[0] = False primes[1] = False sieve(primes, N) tribonacci = [0 for i in range(N+1)] tribonacci[0] = 0 tribonacci[1] = 0 tribonacci[2] = 1 # Generating the sequence using formula # t(i) = t(i-1) + t(i-2) + t(i-3). i = 3 while(tribonacci[i - 1] <= N): tribonacci[i] = tribonacci[i - 1] + tribonacci[i - 2] + tribonacci[i - 3] i += 1 # Store the answer ans = [] # Iterating over all the Tribonacci series i = 0 while(tribonacci[i] <= N): p = tribonacci[i] # Check if the ith tribonacci # is prime or not if (primes[p] == True): ans.append(p) i += 1 return ans# Driver code.N = 10# Function callans = findValues(N)# Printing Tribonacci numbers which are prime.for i in range(len(ans)): print(f"{ans[i]}",end=" ")if (len(ans) == 0): print(-1)# This code is contributed by shinjanpatra |
C#
// C# program to implement// the above approachusing System;using System.Collections.Generic;class GFG{ // Function to find the primes upto N using // Sieve of Eratosthenes technique static void sieve(bool[] primes, int N) { for (int i = 2; i * i <= N; i++) { if (primes[i] == true) { for (int j = i + i; j <= N; j = j + i) { primes[j] = false; } } } } // Function to find the count of the numbers static List<int> findValues(int N) { // Stores all the prime number till n bool[] primes = new bool[N + 1]; for(int i=0; i<N+1; i++) { primes[i] = true; } // 0 and 1 is not prime number primes[0] = false; primes[1] = false; sieve(primes, N); int[] tribonacci = new int[N + 1]; tribonacci[0] = 0; tribonacci[1] = 0; tribonacci[2] = 1; // Generating the sequence using formula // t(i) = t(i-1) + t(i-2) + t(i-3). for (int i = 3; tribonacci[i - 1] <= N; i++) { tribonacci[i] = tribonacci[i - 1] + tribonacci[i - 2] + tribonacci[i - 3]; } // Store the answer List<int> ans = new List<int>(); // Iterating over all the Tribonacci series for (int i = 0; tribonacci[i] <= N; i++) { int p = tribonacci[i]; // Check if the ith tribonacci // is prime or not if (primes[p] == true) { ans.Add(p); } } return ans; } // Driver Code public static void Main() { int N = 10; // Function call List<int> ans = findValues(N); // Printing Tribonacci numbers which are prime. for (int i = 0; i < ans.Count; i++) { Console.Write(ans[i] + " "); } if (ans.Count == 0) Console.Write(-1); }}// This code is contributed by code_hunt. |
Javascript
<script> // JavaScript code to implement the approach // Function to find the primes upto N using // Sieve of Eratosthenes technique const sieve = (primes, N) => { for (let i = 2; i * i <= N; i++) { if (primes[i] == true) { for (let j = i + i; j <= N; j = j + i) { primes[j] = false; } } } } // Function to find the count of the numbers const findValues = (N) => { // Stores all the prime number till n let primes = new Array(N + 1).fill(true); // 0 and 1 is not prime number primes[0] = false; primes[1] = false; sieve(primes, N); let tribonacci = new Array(N + 1).fill(0); tribonacci[0] = 0; tribonacci[1] = 0; tribonacci[2] = 1; // Generating the sequence using formula // t(i) = t(i-1) + t(i-2) + t(i-3). for (let i = 3; tribonacci[i - 1] <= N; i++) { tribonacci[i] = tribonacci[i - 1] + tribonacci[i - 2] + tribonacci[i - 3]; } // Store the answer let ans = []; // Iterating over all the Tribonacci series for (let i = 0; tribonacci[i] <= N; i++) { let p = tribonacci[i]; // Check if the ith tribonacci // is prime or not if (primes[p] == true) { ans.push(p); } } return ans; } // Driver code. let N = 10; // Function call let ans = findValues(N); // Printing Tribonacci numbers which are prime. for (let i = 0; i < ans.length; i++) { document.write(`${ans[i]} `); } if (ans.length == 0) document.write(-1);// This code is contributed by rakeshsahni</script> |
Output
2 7
Time Complexity: O(N*log(log(N)))
Auxiliary space: O(N)
Share your thoughts in the comments
