littlelee
Admin
Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 29
Đến từ : Nghĩa địa
 |  Tiêu đề: Giải bài các số nguyên tố tương đương  Sun 28 Mar 2010, 11:29 | |
| Đề: - Trích dẫn :
- Hai số gọi là nguyên tố tương đương nếu chúng có cùng các ước số nguyên tố. Ví dụ 15 và 75 là các số nguyên tố tương đương. Bởi vì 15=3*5 trong khi 75=3*5^2 , có cùng ước số nguyên tố là 3 và 5. Tương tự 12=2^2*3 và 18=2*3^2 là hai số nguyên tố tương ttương vì có cùng hai ước số nguyên tố là 2 và 3. Tuy nhiên 12 và 60 ko nguyên tố tương đương vì 12=2^2*3 và 60=2^2*3*5, 60 có ước số nguyên tố 5 trong khi 12 không có.
Hãy viết chương trình kiểm tra 2 số có nguyên tố tương hay không.
Mở rộng với n số nguyên tố tương đương.
Dữ liệu của cả hai bài có thể nhập từ bàn phím hay file đều được. Bài giải với hai số:Với dạng này, mình làm kiểu phân tích. Gọi 2 số nhập vào là k và l . Với mọi số i mà k chia hết cho i, ta sẽ rút hết thừa số i trong k ra, đồng thời nếu l chi hết cho i thì ta cũng rút hết thừa số i trong l ra. Ta sẽ tiếp tục như thế cho đến khi k=1. Khi đó nếu l=1 thi hai số k va l nguyên tố tương đương, ngược lại nếu l>1 thì hai số trên không nguyên tố tương đương. Bài cụ thể: - Code:
-
program nguyen_to_tuong_duong;
uses crt;
const max=100;
var a:array[1..max] of integer;
i,n,k,l:integer;
procedure nhap;
begin
clrscr;
write('nhap vao so thu nhat: ');readln(k);
write('nhap vao so thu hai : ');readln(l);
end;
procedure tinh;
begin
if k>l then begin i:=k; k:=l; l:=i; end;
i:=2;
while k<>1 do
begin
while k mod i<>0 do inc(i);
while k mod i=0 do k:=k div i;
while l mod i=0 do l:=l div i;
end;
end;
procedure xuat;
begin
if l=1 then writeln('Hai so vua nhap nguyen to tuong duong.')
else writeln('Hai so vua nhap khong nguyen to tuong duong.');
readln;
end;
begin
nhap;
tinh;
xuat;
end.
Được sửa bởi littlelee ngày Sun 28 Mar 2010, 11:50; sửa lần 1. | |
|
littlelee
Admin
Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 29
Đến từ : Nghĩa địa
| | Tiêu đề: Re: Giải bài các số nguyên tố tương đương Sun 28 Mar 2010, 11:38 | |
| Bài giải với n số:Giải thuật của mình cũng tương tự ^^. Bài cụ thể: - Code:
-
program nguyen_to_tuong_duong;
uses crt;
const max=100;
var a:array[1..max] of integer;
i,j,n,k:integer; ok:boolean;
procedure nhap;
begin
clrscr;
write('nhap so phan tu cua day: ');readln(n);
for i:=1 to n do
begin
write('a[',i,']=');readln(a[i]);
end;
end;
procedure tinh;
begin
k:=a[1];
for i:=2 to n do if a[i]<k then k:=a[i];
i:=2;
while k<>1 do
begin
while k mod i<>0 do inc(i);
while k mod i=0 do k:=k div i;
for j:=1 to n do
while a[j] mod i=0 do a[j]:=a[j] div i;
end;
end;
procedure xuat;
begin
ok:=true;
for i:=1 to n do
if a[i]<>1 then begin ok:=false; break; end;
if ok then writeln('Hai so vua nhap nguyen to tuong duong.')
else writeln('Hai so vua nhap khong nguyen to tuong duong.');
readln;
end;
begin
nhap;
tinh;
xuat;
end. | |
|
