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