Dada una array arr[] de tamaño N , la tarea es encontrar los números compuestos de Fibonacci presentes en la array dada.
Ejemplos:
Entrada: arr[] = {13, 55, 7, 3, 5, 21, 233, 144, 6}
Salida: 55 21 144
Explicación:
Los elementos de array compuesta son {55, 21, 144, 6}.
Los elementos del arreglo de Fibonacci son {55, 21, 144}.
Por lo tanto, los elementos de array que son tanto compuestos como Fibonacci son {55, 21, 144}.Entrada: arr[] = {34, 13, 11, 8, 3, 55, 233}
Salida: 3
Explicación:
Los elementos de la array compuesta son {34, 8, 55}
Los elementos de la array de Fibonacci son {34, 8, 55}
Por lo tanto, los elementos de array que son tanto compuestos como Fibonacci son {34, 8, 55}.
Enfoque: siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos Max para almacenar el elemento más grande de la array .
- Cree un conjunto para almacenar todos los números de Fibonacci hasta Max .
- Inicialice una array , digamos sieve[] , para almacenar todos los números primos usando Sieve Of Eratosthenes .
- Finalmente, recorra la array y verifique si el elemento de la array actual es compuesto y número de Fibonacci o no. Si se encuentra que es cierto, imprima el elemento actual.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find all Fibonacci
// numbers up to Max
set<int> createhashmap(int Max)
{
// Store all Fibonacci numbers
// upto Max
set<int> hashmap;
// Stores previous element
// of Fibonacci sequence
int curr = 1;
// Stores previous element
// of Fibonacci sequence
int prev = 0;
// Insert prev into hashmap
hashmap.insert(prev);
// Insert all the Fibonacci
// numbers up to Max
while (curr <= Max) {
// Insert curr into hashmap
hashmap.insert(curr);
// Stores curr into temp
int temp = curr;
// Update curr
curr = curr + prev;
// Update prev
prev = temp;
}
return hashmap;
}
// Function to find all Composite
// numbers up to Max
vector<bool> SieveOfEratosthenes(
int Max)
{
// isPrime[i]: Stores if i is
// a prime number or not
vector<bool> isPrime(Max, true);
isPrime[0] = false;
isPrime[1] = false;
// Calculate all prime numbers up to
// Max using Sieve of Eratosthenes
for (int p = 2; p * p <= Max; p++) {
// If P is a prime number
if (isPrime[p]) {
// Set all multiple of P
// as non-prime
for (int i = p * p; i <= Max;
i += p) {
// Update isPrime
isPrime[i] = false;
}
}
}
return isPrime;
}
// Function to find the numbers which is
// both a composite and Fibonacci number
int cntFibonacciPrime(int arr[], int N)
{
// Stores the largest element
// of the array
int Max = arr[0];
// Traverse the array arr[]
for (int i = 1; i < N; i++) {
// Update Max
Max = max(Max, arr[i]);
}
// isPrim[i] check i is
// a prime number or not
vector<bool> isPrime
= SieveOfEratosthenes(Max);
// Stores all the Fibonacci numbers
set<int> hashmap
= createhashmap(Max);
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
// current element is not
// a composite number
if (arr[i] == 1)
continue;
// If current element is a Fibonacci
// and composite number
if ((hashmap.count(arr[i]))
&& !isPrime[arr[i]]) {
// Print current element
cout << arr[i] << " ";
}
}
}
// Driver Code
int main()
{
int arr[] = { 13, 55, 7, 3, 5, 21,
233, 144, 89 };
int N = sizeof(arr) / sizeof(arr[0]);
cntFibonacciPrime(arr, N);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
static boolean[] isPrime;
// Function to find all
// Fibonacci numbers up
// to Max
static HashSet<Integer>
createhashmap(int Max)
{
// Store all Fibonacci numbers
// upto Max
HashSet<Integer> hashmap =
new HashSet<>();
// Stores previous element
// of Fibonacci sequence
int curr = 1;
// Stores previous element
// of Fibonacci sequence
int prev = 0;
// Insert prev into hashmap
hashmap.add(prev);
// Insert all the Fibonacci
// numbers up to Max
while (curr < Max)
{
// Insert curr into
// hashmap
hashmap.add(curr);
// Stores curr into
// temp
int temp = curr;
// Update curr
curr = curr + prev;
// Update prev
prev = temp;
}
return hashmap;
}
// Function to find all
// Composite numbers up
// to Max
static void SieveOfEratosthenes(int Max)
{
// isPrime[i]: Stores if i is
// a prime number or not
isPrime = new boolean[Max];
Arrays.fill(isPrime, true);
isPrime[0] = false;
isPrime[1] = false;
// Calculate all prime numbers
// up to Max using Sieve of
// Eratosthenes
for (int p = 2;
p * p <= Max; p++)
{
// If P is a prime number
if (isPrime[p])
{
// Set all multiple of P
// as non-prime
for (int i = p * p; i <= Max;
i += p)
{
// Update isPrime
isPrime[i] = false;
}
}
}
}
// Function to find the numbers which is
// both a composite and Fibonacci number
static void cntFibonacciPrime(int arr[],
int N)
{
// Stores the largest element
// of the array
int Max = arr[0];
// Traverse the array arr[]
for (int i = 1; i < N; i++)
{
// Update Max
Max = Math.max(Max, arr[i]);
}
// isPrim[i] check i is
// a prime number or not
SieveOfEratosthenes(Max);
// Stores all the Fibonacci
// numbers
HashSet<Integer> hashmap =
createhashmap(Max);
// Traverse the array arr[]
for (int i = 0; i < N; i++)
{
// current element is not
// a composite number
if (arr[i] == 1)
continue;
// If current element is a
// Fibonacci and composite
// number
if ((hashmap.contains(arr[i])) &&
!isPrime[arr[i]])
{
// Print current element
System.out.print(arr[i] + " ");
}
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = {13, 55, 7, 3, 5,
21, 233, 144, 89};
int N = arr.length;
cntFibonacciPrime(arr, N);
}
}
// This code is contributed by Princi Singh
Python3
# Python3 program to implement
# the above approach
import math
# Function to find all Fibonacci
# numbers up to Max
def createhashmap(Max):
# Store all Fibonacci numbers
# upto Max
hashmap = {""}
# Stores previous element
# of Fibonacci sequence
curr = 1
# Stores previous element
# of Fibonacci sequence
prev = 0
# Insert prev into hashmap
hashmap.add(prev)
# Insert all the Fibonacci
# numbers up to Max
while (curr <= Max):
# Insert curr into hashmap
hashmap.add(curr)
# Stores curr into temp
temp = curr
# Update curr
curr = curr + prev
# Update prev
prev = temp
return hashmap
# Function to find all Composite
# numbers up to Max
def SieveOfEratosthenes(Max):
# isPrime[i]: Stores if i is
# a prime number or not
isPrime = [1 for x in range(Max + 1)]
isPrime[0] = 0
isPrime[1] = 0
# Calculate all prime numbers up to
# Max using Sieve of Eratosthenes
for p in range(0, int(math.sqrt(Max))):
# If P is a prime number
if (isPrime[p]):
# Set all multiple of P
# as non-prime
for i in range(2 * p, Max, p):
isPrime[i] = 0
return isPrime
# Function to find the numbers which is
# both a composite and Fibonacci number
def cntFibonacciPrime(arr, N):
# Stores the largest element
# of the array
Max = arr[0]
# Traverse the array arr[]
for i in range(0, N):
# Update Max
Max = max(Max, arr[i])
# isPrim[i] check i is
# a prime number or not
isPrime = SieveOfEratosthenes(Max)
# Stores all the Fibonacci numbers
hashmap = createhashmap(Max)
# Traverse the array arr[]
for i in range(0, N):
# Current element is not
# a composite number
if arr[i] == 1:
continue
# If current element is a Fibonacci
# and composite number
if ((arr[i] in hashmap) and
(not(isPrime[arr[i]]))):
# Print current element
print(arr[i], end = " ")
# Driver Code
arr = [ 13, 55, 7, 3, 5,
21, 233, 144, 89 ]
N = len(arr)
cntFibonacciPrime(arr, N)
# This code is contributed by Stream_Cipher
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
static bool[] isPrime;
// Function to find all
// Fibonacci numbers up
// to Max
static HashSet<int> createhashmap(int Max)
{
// Store all Fibonacci numbers
// upto Max
HashSet<int> hashmap = new HashSet<int>();
// Stores previous element
// of Fibonacci sequence
int curr = 1;
// Stores previous element
// of Fibonacci sequence
int prev = 0;
// Insert prev into hashmap
hashmap.Add(prev);
// Insert all the Fibonacci
// numbers up to Max
while (curr < Max)
{
// Insert curr into
// hashmap
hashmap.Add(curr);
// Stores curr into
// temp
int temp = curr;
// Update curr
curr = curr + prev;
// Update prev
prev = temp;
}
return hashmap;
}
// Function to find all
// Composite numbers up
// to Max
static void SieveOfEratosthenes(int Max)
{
// isPrime[i]: Stores if i is
// a prime number or not
isPrime = new bool[Max];
for(int i = 0;i<Max;i++)
isPrime[i] = true;
isPrime[0] = false;
isPrime[1] = false;
// Calculate all prime numbers
// up to Max using Sieve of
// Eratosthenes
for(int p = 2; p * p <= Max; p++)
{
// If P is a prime number
if (isPrime[p])
{
// Set all multiple of P
// as non-prime
for(int i = p * p; i <= Max;
i += p)
{
// Update isPrime
isPrime[i] = false;
}
}
}
}
// Function to find the numbers which is
// both a composite and Fibonacci number
static void cntFibonacciPrime(int []arr,
int N)
{
// Stores the largest element
// of the array
int Max = arr[0];
// Traverse the array []arr
for(int i = 1; i < N; i++)
{
// Update Max
Max = Math.Max(Max, arr[i]);
}
// isPrim[i] check i is
// a prime number or not
SieveOfEratosthenes(Max);
// Stores all the Fibonacci
// numbers
HashSet<int> hashmap = createhashmap(Max);
// Traverse the array []arr
for(int i = 0; i < N; i++)
{
// current element is not
// a composite number
if (arr[i] == 1)
continue;
// If current element is a
// Fibonacci and composite
// number
if ((hashmap.Contains(arr[i])) &&
!isPrime[arr[i]])
{
// Print current element
Console.Write(arr[i] + " ");
}
}
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 13, 55, 7, 3, 5,
21, 233, 144, 89 };
int N = arr.Length;
cntFibonacciPrime(arr, N);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to find all Fibonacci
// numbers up to Max
function createhashmap(Max)
{
// Store all Fibonacci numbers
// upto Max
var hashmap = new Set();
// Stores previous element
// of Fibonacci sequence
var curr = 1;
// Stores previous element
// of Fibonacci sequence
var prev = 0;
// Insert prev into hashmap
hashmap.add(prev);
// Insert all the Fibonacci
// numbers up to Max
while (curr <= Max)
{
// Insert curr into hashmap
hashmap.add(curr);
// Stores curr into temp
var temp = curr;
// Update curr
curr = curr + prev;
// Update prev
prev = temp;
}
return hashmap;
}
// Function to find all Composite
// numbers up to Max
function SieveOfEratosthenes(Max)
{
// isPrime[i]: Stores if i is
// a prime number or not
var isPrime = Array(Max + 1).fill(true);
isPrime[0] = false;
isPrime[1] = false;
// Calculate all prime numbers up to
// Max using Sieve of Eratosthenes
for(var p = 2; p * p <= Max; p++)
{
// If P is a prime number
if (isPrime[p])
{
// Set all multiple of P
// as non-prime
for(var i = p * p; i <= Max;
i += p)
{
// Update isPrime
isPrime[i] = false;
}
}
}
return isPrime;
}
// Function to find the numbers which is
// both a composite and Fibonacci number
function cntFibonacciPrime(arr, N)
{
// Stores the largest element
// of the array
var Max = arr[0];
// Traverse the array arr[]
for(var i = 1; i < N; i++)
{
// Update Max
Max = Math.max(Max, arr[i]);
}
// isPrim[i] check i is
// a prime number or not
var isPrime = SieveOfEratosthenes(Max);
// Stores all the Fibonacci numbers
var hashmap = createhashmap(Max);
// Traverse the array arr[]
for(var i = 0; i < N; i++)
{
// current element is not
// a composite number
if (arr[i] == 1)
continue;
// If current element is a Fibonacci
// and composite number
if (hashmap.has(arr[i]) &&
!isPrime[arr[i]])
{
// Print current element
document.write( arr[i] + " ");
}
}
}
// Driver Code
var arr = [ 13, 55, 7, 3, 5, 21,
233, 144, 89 ];
var N = arr.length;
cntFibonacciPrime(arr, N);
// This code is contributed by itsok
</script>
Producción:
55 21 144
Complejidad de tiempo: O(N + Max * log(log(Max))), donde Max es el elemento más grande de la array
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por crisscross y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA