Giuga Numbers | C ++ program for the above approach ; Function to check if n is a composite number ; Corner cases ; This is checked to skip middle 5 numbers ; Function to check if N is a Giuga Number ; N should be composite to be a Giuga Number ; Print the number of 2 s that divide n ; N must be odd at this point . So we can skip one element ; While i divides n , print i and divide n ; This condition is to handle the case when n is a prime number > 2 ; Driver Code ; Given Number N ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool isComposite ( int n ) { if ( n <= 1 ) return false ; if ( n <= 3 ) return false ; 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 ; } bool isGiugaNum ( int n ) { if ( ! ( isComposite ( n ) ) ) return false ; int N = n ; while ( n % 2 == 0 ) { if ( ( N / 2 - 1 ) % 2 != 0 ) return false ; n = n / 2 ; } for ( int i = 3 ; i <= sqrt ( n ) ; i = i + 2 ) { while ( n % i == 0 ) { if ( ( N / i - 1 ) % i != 0 ) return false ; n = n / i ; } } if ( n > 2 ) if ( ( N / n - 1 ) % n != 0 ) return false ; return true ; } int main ( ) { int N = 30 ; if ( isGiugaNum ( N ) ) cout << " Yes " ; else cout << " No " ; }