আলোচনাঃ
প্রশ্নে বলা হয়েছে, T-prime হবে সেসব নম্বর যাদের exactly 3টা divisor থাকবে।
উত্তরঃ
এখন কাদের always 3টা divisor থাকবে সেটা দেখা যাক,
| numbers | divisors | Total divisor |
| 1 | 1 | 1 |
| 2 | 1, 2 | 2 |
| 2*2 = 4 | 1,2,4 | 3 |
| 6 | 1,2,3,4 | 4 |
| 3*3 = 9 | 1,3,9 | 3 |
| 5*5 = 25 | 1,5,25 | 3 |
| 36 | 1,2,3,4,6,9,12,18,36 or, Prime factorization = 2^2 * 3^2 = (2+1)*(2+1) | 9 |
| 7*7 = 49 | 1,7,49 | 3 |
উপরের ছক থেকে দেখতে পাচ্ছি, “prime number এর square” যেসকল নম্বর তাদের divisor count ই কেবল 3 হচ্ছে।
তাহলে prime number তো আমরা sieve দিয়ে store করে রাখতে পারি। তো এখানে সরাসরি prime number না রেখে prime number টাকে square করে রাখতে পারি।
পরে binary search করে O(logN) এ বের করতে পারি যে, x ; vector এ আছে কি নাই।থাকলে YES,না থাকলে NO প্রিন্ট করব।
C++ Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 100
const int N=1e7;
vector<ll> prime;
bool vis[100000000];
void sieve(){
for(ll i=3;i*i<=N;i+=2){
if(vis[i]==0){
for(ll j=i*i;j<=N;j+=2*i){
vis[j]=1;
}
}
}
prime.push_back(2*2);
for(ll i=3;i<=N;i+=2){
if(vis[i]==0) prime.push_back(i*i);
}
}
int main(){
sieve(); //O(Nlog(logN))
ll n;
cin>>n;
for(ll i=0;i<n;i++){
ll x,flag=0;
cin>>x;
auto it=binary_search(prime.begin(),prime.end(),x); //O(logN)
//binary_search (return type 'bool')
if(it) cout<<"YES\n";
else cout<<"NO\n";
}
return 0;
}
---------------------------------- OR --------------------------------------
#include<bits/stdc++.h>
using namespace std;
bool isPrime(long long int a)
{
if(a<2) return false;
else if(a==2) return true;
else if(a%2==0) return false;
else{
for(int i=3;i*i<=a;i+=2){
if(a%i==0) return false;
}
}
return true;
}
int main()
{
long long int n,y;
int t;
cin>>t;
for(int i=0;i<t;i++){
cin>>n;
y=sqrt(n);
if(y*y==n && isPrime(y)==true) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
/*
As T-prime = square of prime number, that's why we check two conditions:
1) is y=sqrt(n) a prime?
2) y*y = n ( here, y is prime.So, y*y should be square of prime)
*/
}
}