Một số nguyên dương có đúng 3 ước số nguyên dương khác nhau được gọi là số TNUM. Cho trước một dãy N (1 <= N <= 105) số nguyên dương, xác định các số đã cho có phải là số TNUM hay không?
Input: Cho trong tệp TNUM.INP có cấu trúc như sau:
– Dòng đầu tiên ghi số N
– Dòng tiếp theo ghi N số nguyên a1, a2 … an cách nhau bởi một dấu cách (1 ≤ ai ≤ 1012)
Output: Ghi ra tệp TNUM.OUT gồm N dòng, dòng thứ i ghi YES nếu số thứ i là số TNUM, ngược lại thì ghi NO.
Ví dụ:
TNUM.INP | TNUM.OUT |
3
4 5 6 |
YES
NO NO |
Code bằng C++
#include <bits/stdc++.h> using namespace std; long long a[100005]; bool nt[1000005]; bool kt(long long x) { long long x1=sqrt(x); if (x<4) return 0; if (x1*x1!=x) return 0; return 1; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; freopen("tnum.inp","r",stdin); freopen("tnum.out","w",stdout); cin>>n; for (int i=1;i<=1000000;i++) nt[i]=1; nt[1]=0; for (int i=2;i<=sqrt(1000000);i++) if (nt[i]==1) { int j=i*i; while (j<=1000000) { nt[j]=0; j+=i; } } for (int i=1;i<=n;i++) { cin>>a[i]; int pp=sqrt(a[i]); if (kt(a[i])==1&&nt[pp]==1) cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; }
Code bằng Pascal
var n,i:longint; so,can:int64; f1,f2:text; procedure motep; begin asSign(f1,'TNUM.INP'); reset(f1); assign(f2,'TNUM.OUT'); rewrite(f2); end; function ktnt(a:int64):boolean; var j:longword; begin ktnt:=true; if a<2 then ktnt:=false; if a>3 then for j:=2 to trunc(sqrt(a)) do if a mod j=0 then begin ktnt:=false;break; end; end; begin MOTEP; readln(f1,n); for i:=1 to n do begin read(f1,so); can:=trunc(sqrt(so)); if can*can<>so then writeln(f2,'NO') else if ktnt(can) then writeln(f2,'YES') else writeln(f2,'NO'); end; close(f1); close(f2); END. end.