Powerful Number | C ++ 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 program to test above function
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool 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 <= sqrt ( n ) ; factor += 2 ) { int power = 0 ; while ( n % factor == 0 ) { n = n / factor ; power ++ ; } if ( power == 1 ) return false ; } return ( n == 1 ) ; } int main ( ) { isPowerful ( 20 ) ? cout << " YES STRNEWLINE " : cout << " NO STRNEWLINE " ; isPowerful ( 27 ) ? cout << " YES STRNEWLINE " : cout << " NO STRNEWLINE " ; return 0 ; }