Dado un número N, la tarea es encontrar los primos dentro del rango [1, N] , que también forma parte de una serie de Tribonacci que comienza con {0, 0, 1} .
Nota: Una serie de Tribonacci es una serie en la que el siguiente término es la suma de los tres términos anteriores.
Ejemplos:
Entrada: N = 10
Salida: 2 7
Explicación: Los primeros términos son 0, 0, 1, 1, 2, 4, 7, 13.
Los primos en el rango [1, 10] son 2 y 7.Entrada: N = 2
Salida: 2
Enfoque ingenuo: el enfoque más simple es generar una lista de números de Tribonacci en el rango [1, N] y encontrar los números primos en la serie que están en el rango [1, N].
Complejidad temporal: O(N * √N)
Espacio auxiliar : O(N)
Enfoque eficiente: este problema se puede resolver de manera eficiente con base en la siguiente idea:
Genere una lista de números primos usando la criba de Eratóstenes y luego genere el número de Tribonacci mediante la fórmula t(n) = t(n-1)+t(n-2)+t(n-3) y encuentre todos los números primos de la serie .
Siga los pasos a continuación para implementar la idea anterior:
- Genere una lista de números primos utilizando Tamiz de Eratóstenes .
- Iterar de i = 3 a n (donde el n-ésimo número de Tribonacci es al menos N):
- Calcule el i-ésimo número de Tribonacci mediante la fórmula t(n) = t(n-1)+t(n-2)+t(n-3)
- Comprueba si t(n) es primo con la ayuda de los números primos ya calculados.
- Guárdelos en una array (diga answer[] ).
- Finalmente imprime todos los elementos de la respuesta[] .
A continuación se muestra la implementación del enfoque anterior.
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 technique
void 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 numbers
vector<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 approach
import 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 technique
def 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 numbers
def 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 call
ans = 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 approach
using 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>
Producción
2 7
Complejidad de tiempo: O(N*log(log(N)))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por chandramauliguptach y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA