Dado un número N , la tarea es verificar si N es un Número Giuga o no. Si N es un número Giuga , escriba «Sí» , de lo contrario, escriba «No» .
Un número de Giuga es un número compuesto N tal que p divide (N/p – 1) para cada factor primo p de N.
Ejemplos:
Entrada: N = 30
Salida: Sí
Explicación:
30 es un número compuesto cuyos divisores primos son {2, 3, 5}, tal que
2 divide 30/2 – 1 = 14,
3 divide 30/3 – 1 = 9, y
5 divide 30/5 – 1 = 5.Entrada: N = 161
Salida: No
Enfoque: La idea es comprobar si N es un número compuesto o no. Si no es así, escriba «No».
Si N es un número compuesto, encuentre los factores primos de un número y para cada factor primo p verifique si la condición p divide (n/p – 1) es cierta o no. Si la condición anterior es cierta, 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 n is
// a composite number
bool isComposite(int n)
{
// Corner cases
if (n <= 1)
return false;
if (n <= 3)
return false;
// This is checked to skip
// middle 5 numbers
if (n % 2 == 0 || n % 3 == 0)
return true;
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 N is a
// Giuga Number
bool isGiugaNum(int n)
{
// N should be composite to be
// a Giuga Number
if (!(isComposite(n)))
return false;
int N = n;
// Print the number of 2s
// that divide n
while (n % 2 == 0) {
if ((N / 2 - 1) % 2 != 0)
return false;
n = n / 2;
}
// N must be odd at this point.
// So we can skip one element
for (int i = 3; i <= sqrt(n);
i = i + 2) {
// While i divides n,
// print i and divide n
while (n % i == 0) {
if ((N / i - 1) % i != 0)
return false;
n = n / i;
}
}
// This condition is to handle
// the case when n
// is a prime number > 2
if (n > 2)
if ((N / n - 1) % n != 0)
return false;
return true;
}
// Driver Code
int main()
{
// Given Number N
int N = 30;
// Function Call
if (isGiugaNum(N))
cout << "Yes";
else
cout << "No";
}
Java
// Java program for the above approach
class GFG{
// Function to check if n is
// a composite number
static boolean isComposite(int n)
{
// Corner cases
if (n <= 1)
return false;
if (n <= 3)
return false;
// This is checked to skip
// middle 5 numbers
if (n % 2 == 0 || n % 3 == 0)
return true;
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 N is a
// Giuga Number
static boolean isGiugaNum(int n)
{
// N should be composite to be
// a Giuga Number
if (!(isComposite(n)))
return false;
int N = n;
// Print the number of 2s
// that divide n
while (n % 2 == 0)
{
if ((N / 2 - 1) % 2 != 0)
return false;
n = n / 2;
}
// N must be odd at this point.
// So we can skip one element
for(int i = 3; i <= Math.sqrt(n);
i = i + 2)
{
// While i divides n,
// print i and divide n
while (n % i == 0)
{
if ((N / i - 1) % i != 0)
return false;
n = n / i;
}
}
// This condition is to handle
// the case when n
// is a prime number > 2
if (n > 2)
if ((N / n - 1) % n != 0)
return false;
return true;
}
// Driver code
public static void main(String[] args)
{
// Given Number N
int n = 30;
// Function Call
if (isGiugaNum(n))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by Pratima Pandey
Python3
# Python program for the above approach
import math
# Function to check if n is
# a composite number
def isComposite(n):
# Corner cases
if(n <= 1):
return False
if(n <= 3):
return False
# This is checked to skip
# middle 5 numbers
if(n % 2 == 0 or n % 3 == 0):
return True
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 N is a
# Giuga Number
def isGiugaNum(n):
# N should be composite to be
# a Giuga Number
if(not(isComposite(n))):
return False
N = n
# Print the number of 2s
# that divide n
while(n % 2 == 0):
if((int(N / 2) - 1) % 2 != 0):
return False
n = int(n / 2)
# N must be odd at this point.
# So we can skip one element
for i in range(3, int(math.sqrt(n)) + 1, 2):
# While i divides n,
# print i and divide n
while(n % i == 0):
if((int(N / i) - 1) % i != 0):
return False
n = int(n / i)
# This condition is to handle
# the case when n
# is a prime number > 2
if(n > 2):
if((int(N / n) - 1) % n != 0):
return False
return True
# Driver code
# Given Number N
n = 30
if(isGiugaNum(n)):
print("Yes")
else:
print("No")
# This code is contributed by avanitrachhadiya2155
C#
// C# program for the above approach
using System;
class GFG{
// Function to check if n is
// a composite number
static bool isComposite(int n)
{
// Corner cases
if (n <= 1)
return false;
if (n <= 3)
return false;
// This is checked to skip
// middle 5 numbers
if (n % 2 == 0 || n % 3 == 0)
return true;
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 N is a
// Giuga Number
static bool isGiugaNum(int n)
{
// N should be composite to be
// a Giuga Number
if (!(isComposite(n)))
return false;
int N = n;
// Print the number of 2s
// that divide n
while (n % 2 == 0)
{
if ((N / 2 - 1) % 2 != 0)
return false;
n = n / 2;
}
// N must be odd at this point.
// So we can skip one element
for(int i = 3; i <= Math.Sqrt(n);
i = i + 2)
{
// While i divides n,
// print i and divide n
while (n % i == 0)
{
if ((N / i - 1) % i != 0)
return false;
n = n / i;
}
}
// This condition is to handle
// the case when n
// is a prime number > 2
if (n > 2)
if ((N / n - 1) % n != 0)
return false;
return true;
}
// Driver code
static void Main()
{
// Given Number N
int N = 30;
// Function Call
if (isGiugaNum(N))
Console.Write("Yes");
else
Console.Write("No");
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// JavaScript program for the above approach
// Function to check if n is
// a composite number
function isComposite(n)
{
// Corner cases
if (n <= 1)
return false;
if (n <= 3)
return false;
// This is checked to skip
// middle 5 numbers
if (n % 2 == 0 || n % 3 == 0)
return true;
for(let i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return true;
return false;
}
// Function to check if N is a
// Giuga Number
function isGiugaNum(n)
{
// N should be composite to be
// a Giuga Number
if (!(isComposite(n)))
return false;
let N = n;
// Print the number of 2s
// that divide n
while (n % 2 == 0)
{
if ((N / 2 - 1) % 2 != 0)
return false;
n = n / 2;
}
// N must be odd at this point.
// So we can skip one element
for(let i = 3;
i <= Math.sqrt(n);
i = i + 2)
{
// While i divides n,
// print i and divide n
while (n % i == 0)
{
if ((N / i - 1) % i != 0)
return false;
n = n / i;
}
}
// This condition is to handle
// the case when n
// is a prime number > 2
if (n > 2)
if ((N / n - 1) % n != 0)
return false;
return true;
}
// Driver Code
// Given Number N
let n = 30;
// Function Call
if (isGiugaNum(n))
document.write("Yes");
else
document.write("No");
// This code is contributed by susmitakundugoaldanga
</script>
Producción:
Yes