SGU 113 — Nearly prime numbers
枚举一个素因子i,再判断n div i是不是素数就可以.数据太水了,我刚开始的程序有bug,枚举的不是素因子而是任意因子…我shaz…把自己的算法给忘了…刚才看了一下,枚举到的第一个因子一定是素因子(除了1最小的因子啊…),而只对这一个因子进行判断就可以…
不用筛法,朴素判素就能AC.
{
SGU 113; Nearly prime numbers
- sqybi’s code
}
//for my winsty
program sgu113_sqybi;
var
f: boolean;
i, times, cases, n: longint;
function prime(x: longint): boolean;
var
i: longint;
begin
prime := false;
for i:=2 to trunc(sqrt(x)) do
if x mod i = 0 then exit;
prime := true;
end;
begin
readln(cases);
for times:=1 to cases do begin
read(n);
f := false;
for i:=2 to trunc(sqrt(n)) do
if n mod i = 0 then begin
f := prime(n div i);
break;
end;
if f then writeln(’Yes’) else writeln(’No’);
end;
end.
阅读(82 次)