“ Những số nguyên tố khi chia cho 4 dư 1 thì luôn biểu diễn được dưới dạng tỏng của 2 số chính phương”. Kiểm tra N có nguyên tố hay không? Nếu N nguyên tố, kiểm tra xem có thể phân tích N thành tổng của hai số chính phương a và b hay không? Nếu được hãy tìm a và b.
VD: N=16 thông báo “N không là số nguyên tố”
N=17 thông báo “N là tổng của hai số chính phương :1 16”
dùng free pascal
uses crt;
var a,n:longint;
function nt(n:longint):boolean;
var i:longint;
begin
for i:=2 to trunc(sqrt(n)) do
if n mod i = 0 then exit(false);
exit(true);
end;
function cp(n:longint):boolean;
begin
if sqrt(n)=trunc(sqrt(n)) then exit(true);
exit(false);
end;
begin
clrscr;
readln(n);
if nt(n)=true then
begin
if (n mod 4 = 1) or (n=2) then
begin
a:=1;
while (cp(a)=false) or (cp(n-a)=false) do inc(a);
write(n,’ la tong cua 2 so chinh phuong: ‘);
write(a,’ ‘,n-a);
end
else write(‘Khong the phan tich ‘,n,’ thanh tong 2 so chinh phuong’);
end
else write(n,’ khong la so nguyen to’);
readln;
end.