C++ program to check whether a number is Trojan Number

In this article, we will learn how to check whether a given number is a Trojan Number or not in C++. A number is said to be a trojan number if it is a strong number but not a perfect power.

Example

Input: N = 108
Output: Yes

Input: 9
Output: N0

Note: Every trojan number is a strong number but every strong number is not a trojan number only those that cannot represent as x^y where x, y are positive numbers greater than 1.

Check if it is Trojan Number in C++

Approach: We first create a function perfectPower that helps to check a given number n is prefectPower. Then create a function strongNumber to check whether a given number n is a strong number. Finally, check if n is not a perfect power using perfectPower and n is a strong number using strongNumber then return true else return false

#include <bits/stdc++.h>
using namespace std;
// function to check n is prefect power
bool perfectPower(int n){
    if (n == 1)
        return true;
    
    for (int i = 2;i<=sqrt(n);i++){
        int x = 2;
        int p = pow(i, x);

        while(p<=n && p>0){
            if(p == n)
                return true;
            x++;
            p = pow(i, x);
        }
    }
    return false;
}
// function to check n is strong number
bool strongNumber(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 trojan_number(int n){
    if ( !perfectPower(n) && strongNumber(n))
        return true;
    else
        return false;
}
int main(){
    int n;
    cout<<"Enter n value: ";
    cin>>n;
    if (trojan_number(n))
        cout<<"It is a trojan number"<<endl;
    else
        cout<<"It is not a trojan number"<<endl;
}

Output

Enter n value: 108
It is a trojan number

Enter n value: 11
It is not a trojan number

Also, read

Leave a Reply

Your email address will not be published. Required fields are marked *