Given a number N, the task is to check if N is an Giuga Number or not. If N is an Giuga Number then print “Yes” else print “No”.
A Giuga Number is a composite number N such that p divides (N/p – 1) for every prime factor p of N.
Examples:
Input: N = 30
Output: Yes
Explanation:
30 is a composite number whose prime divisors are {2, 3, 5}, such that
2 divides 30/2 – 1 = 14,
3 divides 30/3 – 1 = 9, and
5 divides 30/5 – 1 = 5.Input: N = 161
Output: No
Approach: The idea is to check if N is composite number or not. If not then print “No”.
If N is a composite number then find the prime factors of a number and for each prime factor p check if the condition p divides (n/p – 1) holds true or not. If the above condition holds true then print “Yes” else print “No”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if n is// a composite numberbool 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 Numberbool 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 Codeint main(){ // Given Number N int N = 30; // Function Call if (isGiugaNum(N)) cout << "Yes"; else cout << "No";} |
Java
// Java program for the above approachclass GFG{ // Function to check if n is// a composite numberstatic 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 Numberstatic 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 approachimport 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 = 30if(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 codestatic 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 numberfunction 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 Numberfunction 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 Nlet n = 30;// Function Callif (isGiugaNum(n)) document.write("Yes");else document.write("No"); // This code is contributed by susmitakundugoaldanga </script> |
Output:
Yes
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
