Encuentre números primos en el rango [1, N] que también pertenezca a una serie de Tribonacci

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *