Length of longest Powerful number subsequence in an Array | Python3 program to find the length of Longest Powerful Subsequence in an Array ; Function to check if the number is powerful ; First divide the number repeatedly by 2 ; Check if only 2 ^ 1 divides n , then return false ; Check 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 , 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. ; Function to find the longest subsequence which contain all powerful numbers ; 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 //= 2 NEW_LINE 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 += 1 NEW_LINE DEDENT if ( power == 1 ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT return ( n == 1 ) NEW_LINE DEDENT def longestPowerfulSubsequence ( arr , n ) : NEW_LINE INDENT answer = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( isPowerful ( arr [ i ] ) ) : NEW_LINE INDENT answer += 1 NEW_LINE DEDENT DEDENT return answer NEW_LINE DEDENT arr = [ 6 , 4 , 10 , 13 , 9 , 25 ] NEW_LINE n = len ( arr ) NEW_LINE print ( longestPowerfulSubsequence ( arr , n ) ) NEW_LINE