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 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ụ

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.