Bài toán số có 3 ước – Minh họa bằng C++ và Pascal

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 <= 10⁵) 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 a₁, a₂ … a_n cách nhau bởi một dấu cách (1 ≤ a_i ≤ 10¹²)

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ụ:

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.