Primer Fibonacci | TCS Mockvita 2020

Descripción del problema

Dados dos números N1 y N2 .

1. Encuentre números primos entre N1 y N2 , luego
2. Haz todas las combinaciones únicas posibles de números de la lista de números primos que encontraste en el paso 1.
3. De esta nueva lista, encuentre nuevamente todos los números primos.
4. Encuentre el número A más pequeño y el número B más grande de la segunda lista generada, también cuente de esta lista.
5. Considere el número más pequeño y el más grande como el primer y segundo número para generar series de Fibonacci respectivamente hasta el conteo (Número de números primos en la segunda lista).
6. Imprime el último número de una serie de Fibonacci como salida

Restricciones

2 <= N1, N2 <= 100

N2 – N1 >= 35

Ejemplos:

Entrada:   N1=2, N2 = 40
Salida: 13158006689
Explicación:
Primera lista de primos = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]

Combinación de todos los primos = [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, 171911, 171911, 171911, 171911 , 1729, 1731, 1737, 192, 193, 195, 197, 1911, 1913, 1917, 1923, 1929, 1931, 1937, 232, 233, 235, 237, 2311, 2313, 2317, 23319, 2 292, 293, 295, 297, 2911, 2913, 2917, 2919, 2923, 2931, 2937, 312, 315, 317, 3111, 3113, 3117, 3119, 3123, 3129, 3137, 73, 372, 3 7 , 3711, 3713, 3717, 3719, 3723, 3729, 3731]

Segunda lista principal = [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]

menor ( A ) = 23

más grande ( B ) = 3719
Por lo tanto, el último número de una serie de Fibonacci, es decir, el número 34 de Fibonacci en la serie que tiene 23 y 3719 como los primeros 2 números es 13158006689

Entrada: N1 = 30, N2 = 70
Salida: 2027041
Explicación:

Primera lista prima = [31, 37, 41, 43, 47, 53, 59, 61, 67]

Segunda lista principal generada por combinación de la primera lista principal = [3137, 5953, 5347, 6761, 3761, 4337, 6737, 6131, 3767, 4759, 4153, 3167, 4159, 6143]
Número primo más pequeño en la segunda lista = 3137
Número primo más grande en 2nd list=6761
Por lo tanto, el último número de una serie de Fibonacci, es decir, el número 14 de Fibonacci en la serie que tiene 3137 y 6761 como los primeros 2 números es 2027041

Enfoque: La idea es usar la Criba de Eratóstenes para comprobar que un número en particular es un número primo o no en tiempo O(1). Por lo tanto, itere sobre todos los números de N1 a N2 y almacene todos los números primos en ese rango en una array, y luego use Nested Loop para encontrar todas las combinaciones únicas posibles de los números primos. Finalmente, encuentre los números primos de toda la combinación y luego el mínimo y el máximo de esos números primos. Usando los números primos mínimos y máximos podemos generar la serie de Fibonacci para calcular el último término (Número de números primos en todas las combinaciones) de la serie de Fibonacci.

A continuación se muestra la implementación del enfoque anterior:

// C++ implementation to compute the
// combination of every possible
// prime numbers of the range
 
#include <bits/stdc++.h>
using namespace std;
 
long long maxN = 1e5;
 
// Sieve of Eratosthenes
void sieve(vector<bool>& primes)
{
    for (long long num = 2;
         num * num < maxN; num++) {
        if (primes[num]) {
            for (long long i = num * num;
                       i < maxN; i += num)
                primes[i] = false;
        }
    }
}
 
// Function to find the Nth term of
// of the Fibonacci series
long long solve(long long N1,
                long long N2)
{
    vector<bool> primes(maxN, true);
    // 1 in not prime
    primes[1] = false;
    // generate all prime in range
    // using sieve of eratosthenes
    sieve(primes);
 
    vector<string> filteredPrimes;
    vector<long long> comb;
    set<long long> lst;
 
    // filter required primes and
    // put them into filteredPrimes
    // as strings
    for (long long i = N1; i <= N2; i++)
        if (primes[i])
            filteredPrimes.push_back(
                          to_string(i));
 
    // make all possible combinations
    for (long long i = 0;
         i < (long long)(filteredPrimes.size());
                                        i++) {
        for (long long j = 0;
             j < (long long)(filteredPrimes.size());
                                        j++) {
            if (i == j)
                continue;
 
            string tmp = filteredPrimes[i] +
                         filteredPrimes[j];
            comb.push_back(stoi(tmp));
        }
    }
 
    // Filter only prime numbers
    // for generated combinations
    for (long long x : comb)
        if (primes[x])
            lst.insert(x);
 
    auto it = lst.end();
    it--;
   
    // take smallest and largest element
    long long a = *(lst.begin()), b = *it, c;
 
    // Now find last element
    // of fibonacci series
    for (long long i = 3;
         i <= (long long)(lst.size());
                                 i++) {
        c = a + b;
        a = b;
        b = c;
    }
 
    return c;
}
 
// Driver Code
int main()
{
    long long N1 = 2, N2 = 40;
 
    cout << solve(N1, N2);
 
    return 0;
}

// JavaScript implementation to compute the
// combination of every possible
// prime numbers of the range
 
const maxN = 1e5;
 
// Sieve of Eratosthenes
function sieve(primes)
{
    for (let num = 2; num * num < maxN; num++) {
        if (primes[num] == true) {
            for (let i = num * num; i < maxN; i += num){
                primes[i] = false;
            }
        }
    }
}
 
// Function to find the Nth term of
// of the Fibonacci series
function solve(N1, N2)
{
    let primes = new Array(maxN).fill(true);
     
    // 1 in not prime
    primes[1] = false;
     
    // generate all prime in range
    // using sieve of eratosthenes
    sieve(primes);
 
    let filteredPrimes = new Array();
    let comb = new Array();
    let lst = new Set();
 
    // filter required primes and
    // put them into filteredPrimes
    // as strings
    for (let i = N1; i <= N2; i++)
        if (primes[i] == true)
            filteredPrimes.push(i.toString());
 
 
    // make all possible combinations
    for (let i = 0; i < filteredPrimes.length; i++) {
        for (let j = 0; j < filteredPrimes.length; j++) {
            if (i == j)
                continue;
 
            let tmp = filteredPrimes[i] + filteredPrimes[j];
            comb.push(parseInt(tmp));
        }
    }
     
    // Filter only prime numbers
    // for generated combinations
    for(let i = 0; i < comb.length; i++){
        if(primes[comb[i]] == true){
            lst.add(comb[i]);
        }
    }
     
    // take smallest and largest element
    let a = [...lst].sort(function(a, b){return a-b})[0];
    let b = [...lst].sort(function(a, b){return a-b})[lst.size - 1];
    let c = 0;
 
    // Now find last element
    // of fibonacci series
    for (let i = 3; i <= lst.size; i++) {
        c = a + b;
        a = b;
        b = c;
    }
 
    return c;
}
 
// Driver Code
let N1 = 2;
let N2 = 40;
console.log(solve(N1, N2));
 
// The code is contributed by Gautam goel (gautamgoel962)

13158006689