Compruebe si GCD de todos los números compuestos en una array divisible por K es un número de Fibonacci o no

Posted on by Rudeus Greyrat

Dada la array arr[] que consta de N enteros no negativos y un entero K , la tarea es verificar si el GCD de todos los números compuestos en la array que son divisibles por K es un número de Fibonacci o no. SI se encuentra que es cierto, escriba “Sí” . De lo contrario, escriba “No” .

Ejemplos:

Entrada: arr[] = {13 , 55, 1331, 7, 13, 11, 44, 77, 144, 89}, K = 11
Salida: No
Explicación: Los números compuestos de la array que son divisibles por 11 son {55, 1331, 11, 44, 77}. GCD de estos elementos es igual a 11, que no es un número de Fibonacci.

Entrada: arr[] = {34, 2, 4, 8, 5, 7, 11}, K = 2
Salida: Sí
Explicación: Los números compuestos de la array que son divisibles por 2 son {34, 2, 4, 8} . GCD de estos elementos es igual a 2, que no es un número de Fibonacci.

Enfoque: siga los pasos a continuación para resolver el problema:

  1. Cree una función isComposite() para verificar si un número es un número compuesto o no .
  2. Cree otra función isFibonacci() para verificar si un número es el número de Fibonacci o no .
  3. Inicialice un vector de enteros, digamos compositeset , y otra variable entera gcd para almacenar gcd de los números compuestos de la array que son divisibles por K.
  4. Recorre la array arr[] .
  5. Para cada elemento arr[i] , compruebe si es compuesto y divisible por K o no. Si se encuentra que es cierto, insértelo en el vector compositeset
  6. Calcule el MCD de todos los elementos del conjunto vectorial compuesto y guárdelo en la variable gcd .
  7. Compruebe si gcd es un número de Fibonacci o no .
  8. Si se encuentra que es cierto, escriba «Sí» . De lo contrario, escriba “No”.

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

C++

// C++ Program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if a
// number is composite or not
bool isComposite(int n)
{
    // Corner cases
    if (n <= 1)
        return false;
 
    if (n <= 3)
        return false;
 
    // Check if the number is
    // divisible by 2 or 3 or not
    if (n % 2 == 0 || n % 3 == 0)
 
        return true;
 
    // Check if n is a multiple of
    // any other prime number
    for (int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
 
            return true;
 
    return false;
}
 
// Function to check if a number
// is a Perfect Square or not
bool isPerfectSquare(int x)
{
    int s = sqrt(x);
    return (s * s == x);
}
 
// Function to check if a number
// is a Fibonacci number or not
bool isFibonacci(int n)
{
    // If 5*n^2 + 4 or 5*n^2 - 4 or
    // both are perfect square
    return isPerfectSquare(5 * n * n + 4)
           || isPerfectSquare(5 * n * n - 4);
}
 
// Function to check if GCD of composite
// numbers from the array a[] which are
// divisible by k is a Fibonacci number or not
void ifgcdFibonacci(int a[], int n, int k)
{
    vector<int> compositeset;
 
    // Traverse the array
    for (int i = 0; i < n; i++) {
 
        // If array element is composite
        // and divisible by k
        if (isComposite(a[i]) && a[i] % k == 0) {
            compositeset.push_back(a[i]);
        }
    }
    int gcd = compositeset[0];
 
    // Calculate GCD of all elements in compositeset
    for (int i = 1; i < compositeset.size(); i++) {
        gcd = __gcd(gcd, compositeset[i]);
        if (gcd == 1) {
            break;
        }
    }
 
    // If GCD is Fibonacci
    if (isFibonacci(gcd)) {
        cout << "Yes";
        return;
    }
    cout << "No";
    return;
}
 
// Driver Code
int main()
{
 
    int arr[] = { 34, 2, 4, 8, 5, 7, 11 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
 
    ifgcdFibonacci(arr, n, k);
    return 0;
}

Java

// Java Program for the above approach
import java.util.*;
 
class GFG{
 
// Function to check if a
// number is composite or not
static boolean isComposite(int n)
{
     
    // Corner cases
    if (n <= 1)
        return false;
 
    if (n <= 3)
        return false;
 
    // Check if the number is
    // divisible by 2 or 3 or not
    if (n % 2 == 0 || n % 3 == 0)
        return true;
 
    // Check if n is a multiple of
    // any other prime number
    for(int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return true;
 
    return false;
}
 
// Function to check if a number
// is a Perfect Square or not
static boolean isPerfectSquare(int x)
{
    int s = (int)Math.sqrt(x);
    return (s * s == x);
}
 
// Function to check if a number
// is a Fibonacci number or not
static boolean isFibonacci(int n)
{
     
    // If 5*n^2 + 4 or 5*n^2 - 4 or
    // both are perfect square
    return isPerfectSquare(5 * n * n + 4) ||
           isPerfectSquare(5 * n * n - 4);
}
 
// Function to check if GCD of composite
// numbers from the array a[] which are
// divisible by k is a Fibonacci number or not
static void ifgcdFibonacci(int a[], int n, int k)
{
    Vector<Integer> compositeset = new Vector<>();
 
    // Traverse the array
    for(int i = 0; i < n; i++)
    {
         
        // If array element is composite
        // and divisible by k
        if (isComposite(a[i]) && a[i] % k == 0)
        {
            compositeset.add(a[i]);
        }
    }
    int gcd = compositeset.get(0);
 
    // Calculate GCD of all elements in compositeset
    for(int i = 1; i < compositeset.size(); i++)
    {
        gcd = __gcd(gcd, compositeset.get(i));
         
        if (gcd == 1)
        {
            break;
        }
    }
 
    // If GCD is Fibonacci
    if (isFibonacci(gcd))
    {
        System.out.print("Yes");
        return;
    }
    System.out.print("No");
    return;
}
 
// Recursive function to return gcd of a and b 
static int __gcd(int a, int b) 
{ 
    return b == 0 ? a : __gcd(b, a % b);    
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 34, 2, 4, 8, 5, 7, 11 };
    int n = arr.length;
    int k = 2;
 
    ifgcdFibonacci(arr, n, k);
}
}
 
// This code is contributed by Amit Katiyar

Python3

# Python3 program for the above approach
import math
 
# Function to check if a
# number is composite or not
def isComposite(n):
     
    # Corner cases
    if n <= 1:
        return False
 
    if n <= 3:
        return False
 
    # Check if the number is
    # divisible by 2 or 3 or not
    if n % 2 == 0 or n % 3 == 0:
        return True
 
    # Check if n is a multiple of
    # any other prime number
    i = 5
    while i * i <= n:
        if ((n % i == 0 ) or
            (n % (i + 2) == 0)):
            return True
             
        i += 6   
 
    return False
 
# Function to check if a number
# is a Perfect Square or not
def isPerfectSquare(x):
     
    s = int(math.sqrt(x))
    return (s * s == x)
     
# Function to check if a number
# is a Fibonacci number or not
def isFibonacci(n):
     
    # If 5*n^2 + 4 or 5*n^2 - 4 or
    # both are perfect square
    return (isPerfectSquare(5 * n * n + 4) or
            isPerfectSquare(5 * n * n - 4))
 
# Function to check if GCD of composite
# numbers from the array a[] which are
# divisible by k is a Fibonacci number or not
def ifgcdFibonacci(a,  n,  k):
 
    compositeset = []
 
    # Traverse the array
    for i in range(n):
 
        # If array element is composite
        # and divisible by k
        if (isComposite(a[i]) and a[i] % k == 0):
            compositeset.append(a[i])
     
    gcd = compositeset[0]
 
    # Calculate GCD of all elements in compositeset
    for i in range(1, len(compositeset), 1):
        gcd = math.gcd(gcd, compositeset[i])
         
        if gcd == 1:
            break
     
    # If GCD is Fibonacci
    if (isFibonacci(gcd)):
        print("Yes")
        return
     
    print("No")
    return
 
# Driver Code
if __name__ == "__main__" :
     
    arr = [ 34, 2, 4, 8, 5, 7, 11 ]
    n = len(arr)
    k = 2
     
    ifgcdFibonacci(arr, n, k)
     
# This code is contributed by jana_sayantan

C#

// C# Program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to check if a
// number is composite or not
static bool isComposite(int n)
{
     
    // Corner cases
    if (n <= 1)
        return false;
 
    if (n <= 3)
        return false;
 
    // Check if the number is
    // divisible by 2 or 3 or not
    if (n % 2 == 0 || n % 3 == 0)
        return true;
 
    // Check if n is a multiple of
    // any other prime number
    for(int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return true;
 
    return false;
}
 
// Function to check if a number
// is a Perfect Square or not
static bool isPerfectSquare(int x)
{
    int s = (int)Math.Sqrt(x);
    return (s * s == x);
}
 
// Function to check if a number
// is a Fibonacci number or not
static bool isFibonacci(int n)
{
     
    // If 5*n^2 + 4 or 5*n^2 - 4 or
    // both are perfect square
    return isPerfectSquare(5 * n * n + 4) ||
           isPerfectSquare(5 * n * n - 4);
}
 
// Function to check if GCD of composite
// numbers from the array []a which are
// divisible by k is a Fibonacci number or not
static void ifgcdFibonacci(int []a, int n, int k)
{
    List<int> compositeset = new List<int>();
 
    // Traverse the array
    for(int i = 0; i < n; i++)
    {
         
        // If array element is composite
        // and divisible by k
        if (isComposite(a[i]) && a[i] % k == 0)
        {
            compositeset.Add(a[i]);
        }
    }
    int gcd = compositeset[0];
 
    // Calculate GCD of all elements in compositeset
    for(int i = 1; i < compositeset.Count; i++)
    {
        gcd = __gcd(gcd, compositeset[i]);
         
        if (gcd == 1)
        {
            break;
        }
    }
 
    // If GCD is Fibonacci
    if (isFibonacci(gcd))
    {
        Console.Write("Yes");
        return;
    }
    Console.Write("No");
    return;
}
 
// Recursive function to return gcd of a and b 
static int __gcd(int a, int b) 
{ 
    return b == 0 ? a : __gcd(b, a % b);    
}
 
// Driver Code
public static void Main(String[] args)
{
    int []arr = { 34, 2, 4, 8, 5, 7, 11 };
    int n = arr.Length;
    int k = 2;
 
    ifgcdFibonacci(arr, n, k);
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// Javascript Program for the above approach
 
function __gcd(a, b) {
  if (!b) {
    return a;
  }
 
  return __gcd(b, a % b);
}
 
// Function to check if a
// number is composite or not
function isComposite(n)
{
    // Corner cases
    if (n <= 1)
        return false;
 
    if (n <= 3)
        return false;
 
    // Check if the number is
    // divisible by 2 or 3 or not
    if (n % 2 == 0 || n % 3 == 0)
        return true;
     
    var i;
    // Check if n is a multiple of
    // any other prime number
    for(i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return true;
 
    return false;
}
 
// Function to check if a number
// is a Perfect Square or not
function isPerfectSquare(x)
{
    var s = Math.sqrt(x);
    return (s * s == x);
}
 
// Function to check if a number
// is a Fibonacci number or not
function isFibonacci(n)
{
    // If 5*n^2 + 4 or 5*n^2 - 4 or
    // both are perfect square
    return isPerfectSquare(5 * n * n + 4)
           || isPerfectSquare(5 * n * n - 4);
}
 
// Function to check if GCD of composite
// numbers from the array a[] which are
// divisible by k is a Fibonacci number or not
function ifgcdFibonacci(a, n, k)
{
    var compositeset = [];
     
    var i;
    // Traverse the array
    for (i = 0; i < n; i++) {
 
        // If array element is composite
        // and divisible by k
        if (isComposite(a[i]) && a[i] % k == 0) {
            compositeset.push(a[i]);
        }
    }
    var gcd = compositeset[0];
 
    // Calculate GCD of all elements in compositeset
    for (i = 1; i < compositeset.length; i++) {
        gcd = __gcd(gcd, compositeset[i]);
        if (gcd == 1) {
            break;
        }
    }
 
    // If GCD is Fibonacci
    if (isFibonacci(gcd)) {
        document.write("Yes");
        return;
    }
    document.write("No");
    return;
}
 
// Driver Code
    var arr = [34, 2, 4, 8, 5, 7, 11];
    var n = arr.length;
    var k = 2;
 
    ifgcdFibonacci(arr, n, k);
 
</script>
Producción: 

Yes

 

Complejidad de tiempo: O(N*log(N)), donde N es el tamaño 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

Deja una respuesta

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