Giuga Numbers | Python 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 ; Given Number N ; Function Call
import math NEW_LINE def isComposite ( n ) : NEW_LINE INDENT if ( n <= 1 ) : NEW_LINE INDENT return False NEW_LINE DEDENT if ( n <= 3 ) : NEW_LINE INDENT return False NEW_LINE DEDENT if ( n % 2 == 0 or n % 3 == 0 ) : NEW_LINE INDENT return True NEW_LINE DEDENT i = 5 NEW_LINE while ( i * i <= n ) : NEW_LINE INDENT if ( n % i == 0 or n % ( i + 2 ) == 0 ) : NEW_LINE INDENT return True NEW_LINE DEDENT i += 6 NEW_LINE DEDENT return False NEW_LINE DEDENT def isGiugaNum ( n ) : NEW_LINE INDENT if ( not ( isComposite ( n ) ) ) : NEW_LINE INDENT return False NEW_LINE DEDENT N = n NEW_LINE while ( n % 2 == 0 ) : NEW_LINE INDENT if ( ( int ( N / 2 ) - 1 ) % 2 != 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT n = int ( n / 2 ) NEW_LINE DEDENT for i in range ( 3 , int ( math . sqrt ( n ) ) + 1 , 2 ) : NEW_LINE INDENT while ( n % i == 0 ) : NEW_LINE INDENT if ( ( int ( N / i ) - 1 ) % i != 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT n = int ( n / i ) NEW_LINE DEDENT DEDENT if ( n > 2 ) : NEW_LINE INDENT if ( ( int ( N / n ) - 1 ) % n != 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT return True NEW_LINE DEDENT n = 30 NEW_LINE if ( isGiugaNum ( n ) ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT