Bài 4. (4 điểm): Hai số tự nhiên được gọi là Nguyên tố tương đương nếu chúng có chung các ước
số nguyên tố. Ví dụ các số 75 và 15 là nguyên tố tương đương vì cùng có các ước nguyên tố là 3
và 5. Cho trước hai số tự nhiên N, M. Hãy viết chương trình kiểm tra xem các số này có là
nguyên tố tương đương với nhau hay không.
uses crt;
var i,n,m,k,d:integer;
{---------------chuong-trinh-con-tim-ucln--------------------}
function ucln(x,y:integer):integer;
var t:integer;
begin
while y<>0 do
begin
t:=x mod y;
x:=y;
y:=t;
end;
ucln:=x;
end;
{------------chuong-trinh-con-kiem-tra-so-nguyen-to-------------------}
function nt(b:longint):boolean;
var j:longint;
begin
nt:=true;
if (b=2) or (b=3) then exit;
nt:=false;
if (b=1) or (b mod 2=0) or (b mod 3=0) then exit;
j:=5;
while j<=trunc(sqrt(b)) do
begin
if (b mod j=0) or (b mod (j+2)=0) then exit;
j:=j+6;
end;
nt:=true;
end;
{---------------chuong-trinh-chinh---------------------}
begin
clrscr;
write('Nhap N: '); readln(N);
write('Nhap M: '); readln(M);
d:=0;
k:=ucln(N,M);
for i:=1 to k do
if nt(i) then d:=d+1;
if d>0 then writeln('2 so nay tuong duong voi nhau')
else writeln('2 so nay khong tuong duong voi nhau');
readln;
end.
uses crt;
var i,n,m:integer;
a,b:array[1..100]of integer;
function nt(n:integer):boolean;
begin
if n<2 then nt:=false;
for i:=2 to n div 2 do
if n mod i=0 then nt:=false;
end;
function nttd(n,m:integer):boolean;
var i,j,k,d,dem,s:integer;
a,b:array[1..100]of integer;
begin
nttd:=false;
d:=0;
for j:=1 to n do
if (nt(j))and(n mod j=0) then
begin
inc(d);
a[d]:=j;
end;
dem:=0;
for k:=1 to n do
if (nt(k))and(m mod k=0) then
begin
inc(dem);
b[dem]:=k;
end;
s:=0;
if d=dem then for i:=1 to d do if a[i]=b[i] then
inc(s);
if s=d then nttd:=true else nttd:=false;
end;
BEGIN
clrscr;
write('nhap n,m:');readln(n,m);
if nttd(n,m) then writeln(n,' va ',m,' la nguyen to tuong duong')
else writeln(n,' va ',m,' khong phai la nguyen to tuong duong');
readln;
END.
uses crt;
Var M,N,d,i,luun,luum:integer;
Function USCLN(m,n: integer): integer;
Var r: integer;
Begin
luun:=n;luum:=m;
While n<>0 do
begin
r:=m mod n; m:=n; n:=r;
end;
USCLN:=m;
End;
function nttd:integer;
begin
d:=USCLN(M,N); i:=2;
While d<>1 do
begin
If d mod i =0 then
begin
While d mod i=0 do d:=d div i;
While M mod i=0 do M:=M div i;
While N mod i=0 do N:=N div i;
end;
Inc(i);
end;
If M*N=1 then Write(luum,' va ', luun,' la so nguyen to tuong duong.')
Else Write(luum ,' va ',luun ,' khong phai la so nguyen to tuong duong.');
end;
BEGIN
clrscr;
Write('Nhap M,N:'); Readln(M,N);
nttd;
Readln;
END.
