Given a NumberĀ 
. The task is to check if N is a Trojan Number or not.
Trojan Number is a number that is a strong number but not a perfect power. A number N is known as a strong number if, for every prime divisor or factor p of N, p2 is also a divisor. In other words, every prime factor appears at least twice.
All Trojan numbers are strong. However, not all strong numbers are Trojan numbers: only those that cannot be represented as mk, where m and k are positive integers greater than 1.
Examples:Ā
Ā
Input : N = 108 Output : YES Input : N = 8 Output : NO
Ā
The idea is to store the count of each prime factor and check if the count is greater than 2 then it will be a Strong Number.
This part can easily be calculated by prime factorization through sieve.
The next step is to check if the given number cannot be expressed as xy. To check whether a number is perfect power or not refer to this article.
Below is the implementation of above problem:Ā
Ā
C++
// CPP program to check if a number is// Trojan Number or notĀ
#include <bits/stdc++.h>using namespace std;Ā
// Function to check if a number// can be expressed as x^ybool isPerfectPower(int n){Ā Ā Ā Ā if (n == 1)Ā Ā Ā Ā Ā Ā Ā Ā return true;Ā
Ā Ā Ā Ā // Try all numbers from 2 to sqrt(n) as baseĀ Ā Ā Ā for (int x = 2; x <= sqrt(n); x++) {Ā Ā Ā Ā Ā Ā Ā Ā int y = 2;Ā Ā Ā Ā Ā Ā Ā Ā int p = pow(x, y);Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Keep increasing y while power 'p'Ā Ā Ā Ā Ā Ā Ā Ā // is smaller than n.Ā Ā Ā Ā Ā Ā Ā Ā while (p <= n && p > 0) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (p == n)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return true;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā y++;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā p = pow(x, y);Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā }Ā Ā Ā Ā return false;}Ā
// Function to check if a number is Strongbool isStrongNumber(int n){Ā Ā Ā Ā unordered_map<int, int> count;Ā Ā Ā Ā while (n % 2 == 0) {Ā Ā Ā Ā Ā Ā Ā Ā n = n / 2;Ā Ā Ā Ā Ā Ā Ā Ā count[2]++;Ā Ā Ā Ā }Ā
Ā Ā Ā Ā // count the number for each prime factorĀ Ā Ā Ā 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) {Ā
Ā Ā Ā Ā Ā Ā Ā Ā // minimum number of prime divisorsĀ Ā Ā Ā Ā Ā Ā Ā // should be 2Ā Ā Ā Ā Ā Ā Ā Ā if (b.second == 1) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā flag = 1;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā break;Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā }Ā
Ā Ā Ā Ā if (flag == 1)Ā Ā Ā Ā Ā Ā Ā Ā return false;Ā Ā Ā Ā elseĀ Ā Ā Ā Ā Ā Ā Ā return true;}Ā
// Function to check if a number// is Trojan Numberbool isTrojan(int n){Ā Ā Ā Ā if (!isPerfectPower(n) && isStrongNumber(n))Ā Ā Ā Ā Ā Ā Ā Ā return true;Ā Ā Ā Ā elseĀ Ā Ā Ā Ā Ā Ā Ā return false;}Ā
// Driver Codeint main(){Ā Ā Ā Ā int n = 108;Ā
Ā Ā Ā Ā if (isTrojan(n))Ā Ā Ā Ā Ā Ā Ā Ā cout << "YES";Ā Ā Ā Ā elseĀ Ā Ā Ā Ā Ā Ā Ā cout << "NO";Ā
Ā Ā Ā Ā return 0;} |
Java
// Java program to check if a number is// Trojan Number or notimport java.util.*;Ā
class GFG {Ā
Ā Ā Ā Ā // Function to check if a numberĀ Ā Ā Ā // can be expressed as x^yĀ Ā Ā Ā static boolean isPerfectPower(int n)Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā if (n == 1)Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return true;Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Try all numbers from 2 to sqrt(n) as baseĀ Ā Ā Ā Ā Ā Ā Ā for (int x = 2; x <= Math.sqrt(n); x++) Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā int y = 2;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā int p = (int) Math.pow(x, y);Ā
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // Keep increasing y while power 'p'Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // is smaller than n.Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā while (p <= n && p > 0) Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (p == n) Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return true;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā y++;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā p = (int) Math.pow(x, y);Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā return false;Ā Ā Ā Ā }Ā
Ā Ā Ā Ā // Function to check if a number is StrongĀ Ā Ā Ā static boolean isStrongNumber(int n) Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā HashMap<Integer, Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Integer> count = new HashMap<Integer, Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Integer>();Ā Ā Ā Ā Ā Ā Ā Ā while (n % 2 == 0) Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā n = n / 2;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (count.containsKey(2)) Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā count.put(2, count.get(2) + 1);Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā } Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā elseĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā count.put(2, 1);Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā // count the number for each prime factorĀ Ā Ā Ā Ā Ā Ā Ā for (int i = 3; i <= Math.sqrt(n); i += 2) Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā while (n % i == 0)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā n = n / i;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (count.containsKey(i))Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā count.put(i, count.get(i) + 1);Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā elseĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā count.put(i, 1);Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā if (n > 2)Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (count.containsKey(n))Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā count.put(n, count.get(n) + 1);Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā } Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā elseĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā count.put(n, 1);Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā int flag = 0;Ā
Ā Ā Ā Ā Ā Ā Ā Ā for (Map.Entry<Integer, Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Integer> b : count.entrySet()) Ā Ā Ā Ā Ā Ā Ā Ā {Ā
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // minimum number of prime divisorsĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // should be 2Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (b.getValue() == 1)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā flag = 1;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā break;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā if (flag == 1) Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return false;Ā Ā Ā Ā Ā Ā Ā Ā } Ā Ā Ā Ā Ā Ā Ā Ā elseĀ Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return true;Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā }Ā
Ā Ā Ā Ā // Function to check if a numberĀ Ā Ā Ā // is Trojan NumberĀ Ā Ā Ā static boolean isTrojan(int n) Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā if (!isPerfectPower(n) && isStrongNumber(n))Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return true;Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā elseĀ Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return false;Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā }Ā
Ā Ā Ā Ā // Driver CodeĀ Ā Ā Ā public static void main(String[] args)Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā int n = 108;Ā
Ā Ā Ā Ā Ā Ā Ā Ā if (isTrojan(n)) Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā System.out.println("Yes");Ā Ā Ā Ā Ā Ā Ā Ā } Ā Ā Ā Ā Ā Ā Ā Ā elseĀ Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā System.out.println("No");Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā }} Ā
// This code is contributed by PrinciRaj1992 |
Python3
# Python 3 program to check if a number # is Trojan Number or notfrom math import sqrt, powĀ
# Function to check if a number# can be expressed as x^ydef isPerfectPower(n):Ā Ā Ā Ā if n == 1:Ā Ā Ā Ā Ā Ā Ā Ā return TrueĀ
Ā Ā Ā Ā # Try all numbers from 2 to Ā Ā Ā Ā # sqrt(n) as baseĀ Ā Ā Ā for x in range(2, int(sqrt(n)) + 1):Ā Ā Ā Ā Ā Ā Ā Ā y = 2Ā Ā Ā Ā Ā Ā Ā Ā p = pow(x, y)Ā
Ā Ā Ā Ā Ā Ā Ā Ā # Keep increasing y while power Ā Ā Ā Ā Ā Ā Ā Ā # 'p' is smaller than n.Ā Ā Ā Ā Ā Ā Ā Ā while p <= n and p > 0:Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if p == n:Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return TrueĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā y += 1Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā p = pow(x, y)Ā
Ā Ā Ā Ā return FalseĀ
# Function to check if a number # is Strongdef isStrongNumber(n):Ā Ā Ā Ā count = {i:0 for i in range(n)}Ā Ā Ā Ā while n % 2 == 0:Ā Ā Ā Ā Ā Ā Ā Ā n = n // 2Ā Ā Ā Ā Ā Ā Ā Ā count[2] += 1Ā
Ā Ā Ā Ā # count the number for eachĀ Ā Ā Ā # prime factorĀ Ā Ā Ā for i in range(3,int(sqrt(n)) + 1, 2):Ā Ā Ā Ā Ā Ā Ā Ā while n % i == 0:Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā n = n // iĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā count[i] += 1Ā
Ā Ā Ā Ā if n > 2:Ā Ā Ā Ā Ā Ā Ā Ā count[n] += 1Ā
Ā Ā Ā Ā flag = 0Ā
Ā Ā Ā Ā for key,value in count.items():Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # minimum number of prime Ā Ā Ā Ā Ā Ā Ā Ā # divisors should be 2Ā Ā Ā Ā Ā Ā Ā Ā if value == 1:Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā flag = 1Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā breakĀ Ā Ā Ā Ā Ā Ā Ā Ā if flag == 1:Ā Ā Ā Ā Ā Ā Ā Ā return FalseĀ Ā Ā Ā return TrueĀ
# Function to check if a number# is Trojan Numberdef isTrojan(n):Ā Ā Ā Ā return isPerfectPower(n) == False and isStrongNumber(n)Ā Ā Ā Ā Ā # Driver Codeif __name__ == '__main__':Ā Ā Ā Ā n = 108Ā
Ā Ā Ā Ā if (isTrojan(n)):Ā Ā Ā Ā Ā Ā Ā Ā print("YES")Ā Ā Ā Ā else:Ā Ā Ā Ā Ā Ā Ā Ā print("NO")Ā
# This code is contributed by# Surendra_Gangwar |
C#
// C# program to check if a number is// Trojan Number or notusing System;using System.Collections.Generic;Ā Ā Ā Ā Ā class GFG {Ā
Ā Ā Ā Ā // Function to check if a numberĀ Ā Ā Ā // can be expressed as x^yĀ Ā Ā Ā static bool isPerfectPower(int n)Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā if (n == 1)Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return true;Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Try all numbers from 2 to sqrt(n) as baseĀ Ā Ā Ā Ā Ā Ā Ā for (int x = 2; x <= Math.Sqrt(n); x++) Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā int y = 2;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā int p = (int) Math.Pow(x, y);Ā
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // Keep increasing y while power 'p'Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // is smaller than n.Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā while (p <= n && p > 0) Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (p == n) Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return true;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā y++;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā p = (int) Math.Pow(x, y);Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā return false;Ā Ā Ā Ā }Ā
Ā Ā Ā Ā // Function to check if a number is StrongĀ Ā Ā Ā static bool isStrongNumber(int n) Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Dictionary<int, Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā int> count = new Dictionary<int,Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā int>();Ā Ā Ā Ā Ā Ā Ā Ā while (n % 2 == 0) Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā n = n / 2;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (count.ContainsKey(2)) Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā count[2] = count[2] + 1;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā } Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā elseĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā count.Add(2, 1);Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā // count the number for each prime factorĀ Ā Ā Ā Ā Ā Ā Ā for (int i = 3; i <= Math.Sqrt(n); i += 2) Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā while (n % i == 0)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā n = n / i;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (count.ContainsKey(i))Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā count[i] = count[i] + 1;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā elseĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā count.Add(i, 1);Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā if (n > 2)Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (count.ContainsKey(n))Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā count[n] = count[n] + 1;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā } Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā elseĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā count.Add(n, 1);Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā int flag = 0;Ā
Ā Ā Ā Ā Ā Ā Ā Ā foreach(KeyValuePair<int, int> b in count)Ā Ā Ā Ā Ā Ā Ā Ā {Ā
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // minimum number of prime divisorsĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // should be 2Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (b.Value == 1)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā flag = 1;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā break;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā if (flag == 1) Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return false;Ā Ā Ā Ā Ā Ā Ā Ā } Ā Ā Ā Ā Ā Ā Ā Ā elseĀ Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return true;Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā }Ā
Ā Ā Ā Ā // Function to check if a numberĀ Ā Ā Ā // is Trojan NumberĀ Ā Ā Ā static bool isTrojan(int n) Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā if (!isPerfectPower(n) && Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā isStrongNumber(n))Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return true;Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā elseĀ Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return false;Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā }Ā
Ā Ā Ā Ā // Driver CodeĀ Ā Ā Ā public static void Main(String[] args)Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā int n = 108;Ā
Ā Ā Ā Ā Ā Ā Ā Ā if (isTrojan(n)) Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Console.WriteLine("Yes");Ā Ā Ā Ā Ā Ā Ā Ā } Ā Ā Ā Ā Ā Ā Ā Ā elseĀ Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Console.WriteLine("No");Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā }}Ā
// This code is contributed by Princi Singh |
Javascript
<script>// javascript program to check if a number is// Trojan Number or notĀ
Ā Ā Ā Ā // Function to check if a numberĀ Ā Ā Ā // can be expressed as x^yĀ Ā Ā Ā function isPerfectPower(n) {Ā Ā Ā Ā Ā Ā Ā Ā if (n == 1) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return true;Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Try all numbers from 2 to sqrt(n) as baseĀ Ā Ā Ā Ā Ā Ā Ā for (var x = 2; x <= Math.sqrt(n); x++) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā var y = 2;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā var p = parseInt( Math.pow(x, y));Ā
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // Keep increasing y while power 'p'Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // is smaller than n.Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā while (p <= n && p > 0) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (p == n) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return true;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā y++;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā p = parseInt( Math.pow(x, y));Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā return false;Ā Ā Ā Ā }Ā
Ā Ā Ā Ā // Function to check if a number is StrongĀ Ā Ā Ā function isStrongNumber(n) {Ā Ā Ā Ā Ā Ā Ā Ā var count = new Map();Ā Ā Ā Ā Ā Ā Ā Ā while (n % 2 == 0) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā n = n / 2;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (count.has(2)) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā count.set(2, count.get(2) + 1);Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā } else {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā count.set(2, 1);Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā // count the number for each prime factorĀ Ā Ā Ā Ā Ā Ā Ā for (var i = 3; i <= Math.sqrt(n); i += 2) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā while (n % i == 0) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā n = n / i;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (count.has(i)) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā count.set(i, count.get(i) + 1);Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā } else {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā count.set(i, 1);Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā if (n > 2) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (count.has(n)) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā count.set(n, count.get(n) + 1);Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā } else {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā count.set(n, 1);Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā var flag = 0;Ā const iterator = count[Symbol.iterator]();Ā Ā Ā Ā let itr = iterator.next()Ā Ā Ā Ā for (let i = 0; i < count.size; i++) {Ā Ā Ā Ā Ā Ā Ā Ā console.log(itr.value, itr.done)Ā Ā Ā Ā Ā Ā Ā Ā if (itr.value == 1) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā flag = 1;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā break;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā itr = iterator.next()Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (flag == 1) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return false;Ā Ā Ā Ā Ā Ā Ā Ā } else {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return true;Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā }Ā
Ā Ā Ā Ā // Function to check if a numberĀ Ā Ā Ā // is Trojan NumberĀ Ā Ā Ā function isTrojan(n) {Ā Ā Ā Ā Ā Ā Ā Ā if (!isPerfectPower(n) && isStrongNumber(n)) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return true;Ā Ā Ā Ā Ā Ā Ā Ā } else {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return false;Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā }Ā
Ā Ā Ā Ā // Driver CodeĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā var n = 108;Ā
Ā Ā Ā Ā Ā Ā Ā Ā if (isTrojan(n)) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā document.write("Yes");Ā Ā Ā Ā Ā Ā Ā Ā } else {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā document.write("No");Ā Ā Ā Ā Ā Ā Ā Ā }Ā
// This code contributed by gauravrajput1 </script> |
Output:Ā
YES
Ā
Auxiliary Space: O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? Itās time for a change! Join our DSA course, where weāll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
