Length of longest Powerful number subsequence in an Array | Java 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
class GFG { static boolean isPowerful ( int n ) { while ( n % 2 == 0 ) { int power = 0 ; while ( n % 2 == 0 ) { n /= 2 ; power ++ ; } if ( power == 1 ) return false ; } for ( int factor = 3 ; factor <= Math . sqrt ( n ) ; factor += 2 ) { int power = 0 ; while ( n % factor == 0 ) { n = n / factor ; power ++ ; } if ( power == 1 ) return false ; } return ( n == 1 ) ; } static int longestPowerfulSubsequence ( int arr [ ] , int n ) { int answer = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( isPowerful ( arr [ i ] ) ) answer ++ ; } return answer ; } public static void main ( String [ ] args ) { int arr [ ] = { 6 , 4 , 10 , 13 , 9 , 25 } ; int n = arr . length ; System . out . print ( longestPowerfulSubsequence ( arr , n ) + "NEW_LINE"); } }