কনসেপ্ট
দেওয়া সংখ্যা n সাপেক্ষে, n ট্রোজান নম্বর কিনা তা যাচাই করুন। ট্রোজান নম্বর হল এমন একটি নম্বর যা শক্তিশালী (Strong) কিন্তু পূর্ণ ঘাত (Perfect Power) নয়। একটি নম্বর n শক্তিশালী যদি এর সব প্রাইম ফ্যাক্টর p-এর জন্য p²ও n কে ভাগ করে। অর্থাৎ প্রতিটি প্রাইম ফ্যাক্টর কমপক্ষে দুবার থাকে। মনে রাখবেন সব ট্রোজান নম্বর শক্তিশালী, কিন্তু সব শক্তিশালী নম্বর ট্রোজান নয়: শুধু যেগুলো a^b রূপে প্রকাশ করা যায় না (a,b > 1)।
ইনপুট
n = 72 72 = 6×6×2 = (6²)×2 অর্থাৎ শক্তিশালী কিন্তু পূর্ণ ঘাত নয়।
আউটপুট
YES
ইনপুট
n = 16 16 = 2×2×2×2 = 2⁴ অর্থাৎ শক্তিশালী কিন্তু পূর্ণ ঘাত।
আউটপুট
NO
পদ্ধতি
প্রথমে প্রতিটি প্রাইম ফ্যাক্টরের কাউন্ট স্টোর করুন এবং কাউন্ট >= ২ কিনা চেক করুন (শক্তিশালী নম্বর)। তারপর নম্বরটি 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;
}
int main(){
int n1 = 72;
if (isTrojan1(n1))
cout << "YES";
else
cout << "NO";
return 0;
} আউটপুট
Yes
