अवधारणा
दिए गए संख्या n के संबंध में, यह सत्यापित करना है कि n एक ट्रोजन संख्या है या नहीं। ट्रोजन संख्या को एक ऐसी संख्या के रूप में परिभाषित किया गया है जो बिना पूर्ण घात के एक मजबूत संख्या है। एक संख्या n को मजबूत संख्या माना जाता है यदि, n के प्रत्येक अभाज्य भाजक या गुणनखंड p के लिए, p^2 भी एक भाजक है। दूसरे शब्दों में, प्रत्येक अभाज्य गुणनखंड कम से कम दो बार आता है। याद रखें कि सभी ट्रोजन संख्याएं मजबूत होती हैं। लेकिन इसका विपरीत सत्य नहीं है: केवल वही मजबूत संख्याएं ट्रोजन होती हैं जिन्हें a^b के रूप में दर्शाया नहीं जा सकता, जहां a और b 1 से बड़े धनात्मक पूर्णांक हैं।
उदाहरण
इनपुट - n = 72
72 को 6×6×2 यानी (6^2)×2 के रूप में व्यक्त किया जाता है यानी मजबूत संख्या लेकिन बिना पूर्ण घात के।
आउटपुट - YES
इनपुट - n = 16
16 को 2×2×2×2 यानी 2^4 के रूप में व्यक्त किया जाता है यानी पूर्ण घात के साथ मजबूत संख्या।
आउटपुट - NO
दृष्टिकोण
सबसे पहले, प्रत्येक अभाज्य गुणनखंड की गिनती संग्रहीत करें और जांचें कि क्या गिनती 2 से अधिक है तो यह एक मजबूत संख्या होगी। अगले चरण में, जांचें कि दी गई संख्या को a^b के रूप में व्यक्त किया जा सकता है या नहीं। यदि यह a^b के रूप में व्यक्त नहीं होती है, तो हम कह सकते हैं कि यह पूर्ण घात नहीं है; अन्यथा यह पूर्ण घात है। अंत में, यदि दी गई संख्या बिना पूर्ण घात के मजबूत है, तो संख्या को ट्रोजन संख्या माना जाता है।
C++ कार्यान्वयन
// CPP program to check if a number is Trojan Number or not
#include <bits/stdc++.h>
using namespace std;
bool isPerfectPower1(int n1){
if (n1 == 1)
return true;
for (int x1 = 2; x1 <= sqrt(n1); x1++) {
int y1 = 2;
int p1 = pow(x1, y1);
while (p1 <= n1 && p1 > 0) {
if (p1 == n1)
return true;
y1++;
p1 = pow(x1, y1);
}
}
return false;
}
bool isStrongNumber1(int n1){
unordered_map<int, int> count1;
while (n1 % 2 == 0) {
n1 = n1 / 2;
count1[2]++;
}
for (int i1 = 3; i1 <= sqrt(n1); i1 += 2) {
while (n1 % i1 == 0) {
n1 = n1 / i1;
count1[i1]++;
}
}
if (n1 > 2)
count1[n1]++;
int flag1 = 0;
for (auto b : count1) {
if (b.second == 1) {
flag1 = 1;
break;
}
}
if (flag1 == 1)
return false;
else
return true;
}
bool isTrojan1(int n1){
if (!isPerfectPower1(n1) && isStrongNumber1(n1))
return true;
else
return false;
}
int main(){
int n1 = 72;
if (isTrojan1(n1))
cout << "YES";
else
cout << "NO";
return 0;
}
आउटपुट
Yes