Números primos y Fibonacci

Dado un número, encuentra los números (menores que o iguales a n) que son tanto Fibonacci como primos.

Ejemplos: 

Input : n = 40
Output: 2 3 5 13
Explanation :
Here, range(upper limit) = 40
Fibonacci series upto n is, 1, 
1, 2, 3, 5, 8, 13, 21, 34.
Prime numbers in above series = 2, 3, 5, 13.

Input : n = 100
Output: 2 3 5 13 89
Explanation :
Here, range(upper limit) = 40
Fibonacci series upto n are 1, 1, 2, 
3, 5, 8, 13, 21, 34, 55, 89.
Prime numbers in Fibonacci upto n : 2, 3, 
5, 13, 89.

Una solución simple es iterar para generar todos los números de Fibonacci menores o iguales a n. Para cada número de Fibonacci, comprueba si es primo o no. Si es principal, entonces imprímalo.

Una solución eficiente es usar Sieve para generar todos los números primos hasta n . Después de haber generado números primos, podemos verificar rápidamente si un primo es Fibonacci o no usando la propiedad de que un número es Fibonacci si tiene la forma 5i 2 + 4 o la forma 5i 2 – 4. Consulte esto para obtener más detalles. .

A continuación se muestra la implementación de los pasos anteriores.  

C++

// CPP program to print prime numbers present
// in Fibonacci series.
#include <bits/stdc++.h>
using namespace std;
 
// Function to check perfect square
bool isSquare(int n)
{
    int sr = sqrt(n);
    return (sr * sr == n);
}
 
// Prints all numbers less than or equal to n that
// are both Prime and Fibonacci.
void printPrimeAndFib(int n)
{
    // Using Sieve to generate all primes
    // less than or equal to n.
    bool prime[n + 1];   
    memset(prime, true, sizeof(prime));
    for (int p = 2; p * p <= n; p++) {
 
        // If prime[p] is not changed, then
        // it is a prime
        if (prime[p] == true) {
 
            // Update all multiples of p
            for (int i = p * 2; i <= n; i += p)
                prime[i] = false;
        }
    }
 
    // Now traverse through the range and print numbers
    // that are both prime and Fibonacci.
    for (int i=2; i<=n; i++)   
       if (prime[i] && (isSquare(5 * i * i + 4) > 0 ||
                        isSquare(5 * i * i - 4) > 0))
                cout << i << " ";
}
 
// Driver function
int main()
{
    int n = 30;
    printPrimeAndFib(n);
    return 0;
}

Java

// Java program to print prime numbers
// present in Fibonacci series.
class PrimeAndFib
{
// Function to check perfect square
Boolean isSquare(int n)
{
    int sr = (int)Math.sqrt(n);
    return (sr * sr == n);
}
 
// Prints all numbers less than or equal
// to n that are both Prime and Fibonacci.
static void printPrimeAndFib(int n)
{
    // Using Sieve to generate all
    // primes less than or equal to n.
    Boolean[] prime = new Boolean[n + 1];
     
    // memset(prime, true, sizeof(prime));
    for (int p = 0; p <= n; p++)
    prime[p] = true;
    for (int p = 2; p * p <= n; p++) {
 
        // If prime[p] is not changed,
        // then it is a prime
        if (prime[p] == true) {
 
            // Update all multiples of p
            for (int i = p * 2; i <= n; i += p)
                prime[i] = false;
        }
    }
 
    // Now traverse through the range and
    // print numbers that are both prime
    // and Fibonacci.
    for (int i=2; i<=n; i++) {
        double sqrt = Math.sqrt(5 * i * i + 4);
        double sqrt1 = Math.sqrt(5 * i * i - 4);
     
        int x = (int) sqrt;
        int y = (int) sqrt1;
 
    if (prime[i]==true && (Math.pow(sqrt,2) ==
        Math.pow(x,2) || Math.pow(sqrt1,2) ==
        Math.pow(y,2)))
        System.out.print(i+" ");
    }
}
 
// driver program
public static void main(String s[])
{
    int n = 30;
    printPrimeAndFib(n);
}
}
 
// This code is contributed by Prerna Saini

Python3

# Python 3 program to print
# prime numbers present in
# Fibonacci series.
import math
 
# Function to check perfect square
def isSquare(n) :
    sr = (int)(math.sqrt(n))
    return (sr * sr == n)
 
 
# Prints all numbers less than
# or equal to n that  are
# both Prime and Fibonacci.
def printPrimeAndFib(n) :
     
    # Using Sieve to generate all
    # primes less than or equal to n.
    prime =[True] * (n + 1)
    p = 2
    while(p * p <= n ):
         
        # If prime[p] is not changed,
        # then it is a prime
        if (prime[p] == True) :
             
            # Update all multiples of p
            for i in range(p * 2, n + 1, p) :
                prime[i] = False
                 
        p = p + 1
     
    # Now traverse through the range
    # and print numbers that are
    # both prime and Fibonacci.
    for i in range(2, n + 1) :
        if (prime[i] and (isSquare(5 * i * i + 4) > 0 or
             isSquare(5 * i * i - 4) > 0)) :
            print(i , " ",end="")
 
 
# Driver function
n = 30
printPrimeAndFib(n);
 
 
# This code is contributed
# by Nikita Tiwari.

C#

// C# program to print prime numbers
// present in Fibonacci series.
using System;
 
class GFG {
     
    // Function to check perfect square
    static bool isSquare(int n)
    {
        int sr = (int)Math.Sqrt(n);
         
        return (sr * sr == n);
    }
      
    // Prints all numbers less than or equal
    // to n that are both Prime and Fibonacci.
    static void printPrimeAndFib(int n)
    {
         
        // Using Sieve to generate all
        // primes less than or equal to n.
        bool[] prime = new bool[n + 1];
          
        // memset(prime, true, sizeof(prime));
        for (int p = 0; p <= n; p++)
            prime[p] = true;
             
        for (int p = 2; p * p <= n; p++) {
      
            // If prime[p] is not changed,
            // then it is a prime
            if (prime[p] == true) {
      
                // Update all multiples of p
                for (int i = p * 2; i <= n; i += p)
                    prime[i] = false;
            }
        }
      
        // Now traverse through the range and
        // print numbers that are both prime
        // and Fibonacci.
        for (int i = 2; i <= n; i++) {
             
            double sqrt = Math.Sqrt(5 * i * i + 4);
            double sqrt1 = Math.Sqrt(5 * i * i - 4);
          
            int x = (int) sqrt;
            int y = (int) sqrt1;
      
        if (prime[i] == true && (Math.Pow(sqrt, 2) ==
             Math.Pow(x, 2) || Math.Pow(sqrt1, 2) ==
                                    Math.Pow(y, 2)))
            Console.Write(i + " ");
        }
    }
      
    // driver program
    public static void Main()
    {
        int n = 30;
         
        printPrimeAndFib(n);
    }
}
  
// This code is contributed by Anant Agarwal.

PHP

<?php
// PHP program to print prime numbers
// present in Fibonacci series.
 
// Function to check perfect square
function isSquare($n)
{
    $sr = (int)sqrt($n);
    return ($sr * $sr == $n);
}
 
// Prints all numbers less than or equal
// to n that are both Prime and Fibonacci.
function printPrimeAndFib($n)
{
    // Using Sieve to generate all primes
    // less than or equal to n.
    $prime = array_fill(0, $n + 1, true);
    for ($p = 2; $p * $p <= $n; $p++)
    {
 
        // If prime[p] is not changed,
        // then it is a prime
        if ($prime[$p] == true)
        {
 
            // Update all multiples of p
            for ($i = $p * 2;
                 $i <= $n; $i += $p)
                $prime[$i] = false;
        }
    }
 
    // Now traverse through the range
    // and print numbers that are both
    // prime and Fibonacci.
    for ($i = 2; $i <= $n; $i++)
    if ($prime[$i] && (isSquare(5 * $i * $i + 4) > 0 ||
                       isSquare(5 * $i * $i - 4) > 0))
        echo $i . " ";
}
 
// Driver Code
$n = 30;
printPrimeAndFib($n);
 
// This code is contributed by mits
?>

Javascript

<script>
 
// Javascript program to print prime numbers
// present in Fibonacci series.
 
// Function to check perfect square
function isSquare(n)
{
    let sr = Math.sqrt(n);
    return (sr * sr == n);
}
   
// Prints all numbers less than or equal
// to n that are both Prime and Fibonacci.
function prletPrimeAndFib(n)
{
    // Using Sieve to generate all
    // primes less than or equal to n.
    let prime = [];
       
    // memset(prime, true, sizeof(prime));
    for (let p = 0; p <= n; p++)
    prime[p] = true;
    for (let p = 2; p * p <= n; p++) {
   
        // If prime[p] is not changed,
        // then it is a prime
        if (prime[p] == true) {
   
            // Update all multiples of p
            for (let i = p * 2; i <= n; i += p)
                prime[i] = false;
        }
    }
   
    // Now traverse through the range and
    // print numbers that are both prime
    // and Fibonacci.
    for (let i=2; i<=n; i++) {
        let sqrt = Math.sqrt(5 * i * i + 4);
        let sqrt1 = Math.sqrt(5 * i * i - 4);
       
        let x = Math.floor(sqrt);
        let y = Math.floor(sqrt1);
   
    if (prime[i]==true && (Math.pow(sqrt,2) ==
        Math.pow(x,2) || Math.pow(sqrt1,2) ==
        Math.pow(y,2)))
        document.write(i+" ");
    }
}
     
// Driver code
 
    let n = 30;
    printPrimeAndFib(n);
           
</script>

Producción: 

2 3 5 13

 Complejidad de tiempo: O (nloglogn)

Espacio Auxiliar: O(n)
 

Publicación traducida automáticamente

Artículo escrito por Abhishek Sharma 44 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 *