Check if a number is a Trojan Number | CPP 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool isPerfectPower ( int n ) { if ( n == 1 ) return true ; for ( int x = 2 ; x <= sqrt ( n ) ; x ++ ) { int y = 2 ; int p = pow ( x , y ) ; while ( p <= n && p > 0 ) { if ( p == n ) return true ; y ++ ; p = pow ( x , y ) ; } } return false ; } bool isStrongNumber ( int n ) { unordered_map < int , int > count ; while ( n % 2 == 0 ) { n = n / 2 ; count [ 2 ] ++ ; } for ( int i = 3 ; i <= sqrt ( n ) ; i += 2 ) { while ( n % i == 0 ) { n = n / i ; count [ i ] ++ ; } } if ( n > 2 ) count [ n ] ++ ; int flag = 0 ; for ( auto b : count ) { if ( b . second == 1 ) { flag = 1 ; break ; } } if ( flag == 1 ) return false ; else return true ; } bool isTrojan ( int n ) { if ( ! isPerfectPower ( n ) && isStrongNumber ( n ) ) return true ; else return false ; } int main ( ) { int n = 108 ; if ( isTrojan ( n ) ) cout << " YES " ; else cout << " NO " ; return 0 ; }