BÀI TẬP 72: SỐ NGUYÊN TỐ TƯƠNG ĐƯƠNG

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ố. Hãy viết chương trình kiểm tra xem hai số tự nhiên m và n được nhập từ bàn phím có là nguyên tố tương đương với nhau hay không?

Yêu cầu: Nhập hai số tự nhiên m và n (0 < m, n ≤ 10⁹), xuất kết quả kiểm tra trên màn hình.

Ví dụ: nhập n =75 và m = 15. Kết quả: 75 và 15 la hai so nguyen to tuong duong.

CODE THAM KHẢO:

uses crt;

var n,m,i:longint; t:boolean;

begin

        clrscr;

        write('Nhap N = '); readln(n);

        write('Nhap M = '); readln(M);

        write(n,' va ',m);

        i:=2;  t:=true;

        repeat

                if n mod i = 0 then

                begin

                        if m mod i <>0 then t:=false;

                        while n mod i =0 do n:=n div i;

                        while m mod i =0 do m:=m div i;

                        if ((n=1) and (m<>1)) or ((n<>1) and (m=1)) then t:=false;

                end;

                i:=i+1;

                if i>sqrt(n) then i:=n;

        until (n=1) or (m=1);

        if t then write(' la hai so nguyen to tuong duong')

        else write(' khong phai so nguyen to tuong duong');

        readln;

end.