02/10/2018, 13:56
BCFACTOR spoj – Phân tích ra thừa số nguyên tố
Nguồn đề bài http://www.spoj.com/PTIT/problems/BCFACTOR/ 1. Đề bài BCFACTOR spoj Cho số nguyên dương n (2<=n<=10^9) , hãy phân tích n ra thừa số nguyên tố. Dữ liệu Một dòng duy nhất chứa số n. Kết quả Mỗi dòng ghi một thừa số nguyên tố và số mũ tương ứng cách nhau ...
Nguồn đề bài http://www.spoj.com/PTIT/problems/BCFACTOR/
1. Đề bài BCFACTOR spoj
Cho số nguyên dương n (2<=n<=10^9) , hãy phân tích n ra thừa số nguyên tố.
Dữ liệu
Một dòng duy nhất chứa số n.
Kết quả
Mỗi dòng ghi một thừa số nguyên tố và số mũ tương ứng cách nhau bởi dấu cách.
Các thừa số nguyên tố in ra theo thứ tự tăng dần.
Ví dụ
| INPUT | OUTPUT |
| 4 | 2 2 |
| INPUT | OUTPUT |
| 168 | 2 33 17 1 |
2. Hướng dẫn BCFACTOR spoj
Theo toán học 1 số chỉ có thể chia hết cho các số từ 1 đến căn bậc 2 của số đó. vì vậy chỉ cần duyệt đếm kết quả nếu chia hết N cho i, với i từ 2-> sqrt(n). ở mỗi bước ta phải cập nhật lại N. thực hiện cho đến khi n=1.
3. code tham khảo BCFACTOR spoj
const fi=';
nmax=31622;
type data=longint;
var
f:text;
n,i,x:data;
A:array[1..nmax] of data;
begin
assign(f,fi); reset(f);
readln(f,n);
close(f);
x:=trunc(sqrt(n));
for i:=2 to x do
A[i]:=0;
for i:=2 to x do
begin
while n mod i = 0 do
begin
inc(a[i]);
n:=n div i;
end;
if n = 1 then
break;
end;
for i:=2 to x do
if a[i]<>0 then
writeln(i,' ',a[i]);
if n>1 then writeln(n,' ',1);
//readln;
end.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | const fi='; nmax=31622; type data=longint; var f:text; n,i,x:data; A:array[1..nmax] of data; begin assign(f,fi); reset(f); readln(f,n); close(f); x:=trunc(sqrt(n)); for i:=2 to x do A[i]:=0; for i:=2 to x do begin while n mod i = 0 do begin inc(a[i]); n:=n div i; end; if n = 1 then break; end; for i:=2 to x do if a[i]<>0 then writeln(i,' ',a[i]); if n>1 then writeln(n,' ',1); //readln; end. |
