Check if a number is an Achilles number or not | Program to check if the given number is an Achilles Number ; function to check if the number is powerful number ; First divide the number repeatedly by 2 ; If only 2 ^ 1 divides n ( not higher powers ) , then return false ; if n is not a power of 2 then this loop will execute repeat above process ; Find highest power of " factor " that divides n ; If only factor ^ 1 divides n ( not higher powers ) , then return false ; n must be 1 now if it is not a prime number . Since prime numbers are not powerful , we return false if n is not 1. ; Utility function to check if number is a perfect power or not ; Function to check Achilles Number ; Driver Code
from math import sqrt , log NEW_LINE def isPowerful ( n ) : NEW_LINE INDENT while ( n % 2 == 0 ) : NEW_LINE INDENT power = 0 NEW_LINE while ( n % 2 == 0 ) : NEW_LINE INDENT n /= 2 NEW_LINE power += 1 NEW_LINE DEDENT if ( power == 1 ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT p = int ( sqrt ( n ) ) + 1 NEW_LINE for factor in range ( 3 , p , 2 ) : NEW_LINE INDENT power = 0 NEW_LINE while ( n % factor == 0 ) : NEW_LINE INDENT n = n / factor NEW_LINE power += 1 NEW_LINE DEDENT if ( power == 1 ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT return ( n == 1 ) NEW_LINE DEDENT def isPower ( a ) : NEW_LINE INDENT if ( a == 1 ) : NEW_LINE INDENT return True NEW_LINE DEDENT p = int ( sqrt ( a ) ) + 1 NEW_LINE for i in range ( 2 , a , 1 ) : NEW_LINE INDENT val = log ( a ) / log ( i ) NEW_LINE if ( ( val - int ( val ) ) < 0.00000001 ) : NEW_LINE INDENT return True NEW_LINE DEDENT DEDENT return False NEW_LINE DEDENT def isAchillesNumber ( n ) : NEW_LINE INDENT if ( isPowerful ( n ) == True and isPower ( n ) == False ) : NEW_LINE INDENT return True NEW_LINE DEDENT else : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 72 NEW_LINE if ( isAchillesNumber ( n ) ) : NEW_LINE INDENT print ( " YES " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " NO " ) NEW_LINE DEDENT n = 36 NEW_LINE if ( isAchillesNumber ( n ) ) : NEW_LINE INDENT print ( " YES " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " NO " ) NEW_LINE DEDENT DEDENT