अवधारणा
दिए गए नंबर n के संबंध में, कार्य यह सत्यापित करना है कि n एक ट्रोजन नंबर है या नहीं। ट्रोजन नंबर को एक ऐसी संख्या के रूप में परिभाषित किया गया है जो एक पूर्ण शक्ति के बिना एक मजबूत संख्या है। हम कह सकते हैं कि एक संख्या n को एक मजबूत संख्या के रूप में माना जाता है, यदि प्रत्येक अभाज्य भाजक या n के कारक p के लिए, p^2 भी एक भाजक है। हम दूसरे तरीके से कह सकते हैं, प्रत्येक अभाज्य गुणनखंड कम से कम दो बार प्रकट होता है। हमें याद रखना चाहिए कि सभी ट्रोजन नंबर मजबूत होते हैं। लेकिन इसके विपरीत यह सच नहीं है कि, सभी मजबूत संख्याएं ट्रोजन संख्याएं नहीं हैं:केवल वे जिन्हें a^b के रूप में प्रदर्शित नहीं किया जा सकता है, जहां a और b सकारात्मक पूर्णांक 1 से अधिक हैं।
इनपुट
n = 72 72 is expressed as 6×6×2 i.e. (6^2)×2 i.e. Strong Number but without perfect power.
आउटपुट
YES
इनपुट
n = 16 16 is expressed as 2×2×2×2 i.e. 2^4 i.e. Strong number with perfect power.
आउटपुट
NO
दृष्टिकोण
सबसे पहले, हमें प्रत्येक अभाज्य गुणनखंड की संख्या को संग्रहीत करना होगा और सत्यापित करना होगा कि यदि गिनती 2 से अधिक है तो यह एक प्रबल संख्या होगी।
अगले चरण के मामले में, हमें यह सत्यापित करना होगा कि दी गई संख्या a^b के रूप में व्यक्त की गई है या नहीं। यदि इसे a^b के रूप में व्यक्त नहीं किया जाता है, तो हम कह सकते हैं कि यह पूर्ण शक्ति है; अन्यथा यह पूर्ण शक्ति है। अंत में, अंतिम चरण में, हम यह निष्कर्ष निकाल सकते हैं कि यदि यह दी गई संख्या पूर्ण शक्ति के बिना मजबूत है, तो संख्या को ट्रोजन नंबर माना जाता है।
उदाहरण
// 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;
}
// Driver Code
int main(){
int n1 = 72;
if (isTrojan1(n1))
cout << "YES";
else
cout << "NO";
return 0;
} आउटपुट
YES