Check if a number is a Trojan Number | Python 3 program to check if a number is Trojan Number or not ; Function to check if a number can be expressed as x ^ y ; Try all numbers from 2 to sqrt ( n ) as base ; Keep increasing y while power ' p ' is smaller than n . ; Function to check if a number is Strong ; count the number for each prime factor ; minimum number of prime divisors should be 2 ; Function to check if a number is Trojan Number ; Driver Code
from math import sqrt , pow NEW_LINE def isPerfectPower ( n ) : NEW_LINE INDENT if n == 1 : NEW_LINE INDENT return True NEW_LINE DEDENT for x in range ( 2 , int ( sqrt ( n ) ) + 1 ) : NEW_LINE INDENT y = 2 NEW_LINE p = pow ( x , y ) NEW_LINE while p <= n and p > 0 : NEW_LINE INDENT if p == n : NEW_LINE INDENT return True NEW_LINE DEDENT y += 1 NEW_LINE p = pow ( x , y ) NEW_LINE DEDENT DEDENT return False NEW_LINE DEDENT def isStrongNumber ( n ) : NEW_LINE INDENT count = { i : 0 for i in range ( n ) } NEW_LINE while n % 2 == 0 : NEW_LINE INDENT n = n // 2 NEW_LINE count [ 2 ] += 1 NEW_LINE DEDENT for i in range ( 3 , int ( sqrt ( n ) ) + 1 , 2 ) : NEW_LINE INDENT while n % i == 0 : NEW_LINE INDENT n = n // i NEW_LINE count [ i ] += 1 NEW_LINE DEDENT DEDENT if n > 2 : NEW_LINE INDENT count [ n ] += 1 NEW_LINE DEDENT flag = 0 NEW_LINE for key , value in count . items ( ) : NEW_LINE INDENT if value == 1 : NEW_LINE INDENT flag = 1 NEW_LINE break NEW_LINE DEDENT DEDENT if flag == 1 : NEW_LINE INDENT return False NEW_LINE DEDENT return True NEW_LINE DEDENT def isTrojan ( n ) : NEW_LINE INDENT return isPerfectPower ( n ) == False and isStrongNumber ( n ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 108 NEW_LINE if ( isTrojan ( n ) ) : NEW_LINE INDENT print ( " YES " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " NO " ) NEW_LINE DEDENT DEDENT