Powerful Number | Python program to find if a number is powerful or not . ; function to check if the number is powerful ; 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 numenr . Since prime numbers are not powerful , we return false if n is not 1. ; Driver code
import math 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 = n // 2 NEW_LINE power = power + 1 NEW_LINE DEDENT if ( power == 1 ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT for factor in range ( 3 , int ( math . sqrt ( n ) ) + 1 , 2 ) : NEW_LINE INDENT power = 0 NEW_LINE while ( n % factor == 0 ) : NEW_LINE INDENT n = n // factor NEW_LINE power = power + 1 NEW_LINE DEDENT if ( power == 1 ) : NEW_LINE INDENT return false NEW_LINE DEDENT DEDENT return ( n == 1 ) NEW_LINE DEDENT print ( " YES " if isPowerful ( 20 ) else " NO " ) NEW_LINE print ( " YES " if isPowerful ( 27 ) else " NO " ) NEW_LINE