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ụ

INPUTOUTPUT
42 2
INPUTOUTPUT
1682 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.

4 thoughts on “BCFACTOR spoj – Phân tích ra thừa số nguyên tố

  1. ad nhầm to rồi, chả có định lý nào trong toán học mà bảo là: “một số chỉ chia hết cho các số từ 1 đến cbh của số đó”. vd: cbh(15)=3 . mà 15 lại chia hết cho 5 , hiển nhiên 5 > cbh(15) => sai bét nhè

    • mình nhấn mạnh là “có thể chia hết” mà bạn, bạn trích dẫn sai câu mình nói rồi nha.
      Còn ví dụ của bạn 15 chia hết cho 1 = 15, 15 chia hết cho 3 = 5, như vậy bạn biết rõ 15 chia hết cho 3 =5 thì không cần phải xét 15 chia cho 5 làm gì có đúng không? nên không phải xét hết từ 2 -> 14 mà chỉ cần xét 2->3 thôi là biết nó có ước số khác 1 và chính nó ko?

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *