不简单的判断素数 pascal

Description

给一个数n（ 0< n < = 10^9 )
如果是素数，那么输出 'YES'
否则输出
n= a1^p1+a2^p2......
其中a1、a2、...为n的质因数，p1,p2,....为对应质因数的幂。但p为1的时候忽略
多组测试数据

Input

11
18
12

Output

YES
18=2*3^2
12=2^2*3

var
n,i,j,m:longint;
x:array[0..100000]of longint;
a:array[2..100000]of longint;
yes:boolean;
begin
while not eof do
begin
fillchar(x,sizeof(x),0);
fillchar(a,sizeof(a),0);
readln(m); n:=m;
i:=2; j:=1; yes:=true;
while (i<>(trunc(sqrt(m))+1)) and (n<>1) do
if n mod i=0 then
begin
yes:=false;
n:=n div i;
if x[j-1]<>i then
begin
x[j]:=i;
inc(j);
end;
inc(a[i]);
end
else inc(i);
if yes then writeln('YES')
else begin
write(m,'=');
for i:=1 to j-2 do
if a[x[i]]=1 then write(x[i],'*')
else write(x[i],'^',a[x[i]],'*');
if a[x[j-1]]<>1 then writeln(x[j-1],'^',a[x[j-1]])
else writeln(x[j-1]);
end;
end;
end.

思想：搜索

DFS产生质因子分解形式

判断素数可以枚举变量i，从2开始到n的平方根，判断n除以i的余数是否为0，如果对于各个i值，n除以它的余数都不为0，那么n就是个素数了。循环只到n的平方根就可以停止是因为如果n的某个质因子大于n的平方根，那么n肯定有个质因子小于其平方根。

要把一个合数分解，可以枚举素数，用各个素数除n。但是并不用找出素数，可以枚举变量a，从2开始，当n被a整除时，就不断用n除以a，知道n不被a整除，即找出它的幂；当n不被a整除时，就增加a。当a大于n时，说明已经把n分解完了。对于题目中n可达10^9，在n被a整除，找出a的幂后，判断一下此时的n是否素数，如果是素数，那么就可以停止了。这样判断素数最多也就判断十几次，大大减少了耗时。

1、判断素数简单，只需要判断余数就行 2、分解，不怎么明白 比如，36，分解出来是啥？ 2^2*3^2还是36=2*3^2＋2*3^2

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息