ধারণা
প্রদত্ত সংখ্যা 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
