Nguồn đề bài http://www.spoj.com/PTIT/problems/BCFACTOR/
Nội dung bài viết
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
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. |
Bài viết liên quan
- PTIT016E spoj PTIT – ACM PTIT 2016 E – Kỳ thi ACM/ICPC
- MYSTERY spoj – Số huyền bí
- BCCOM spoj PTIT – Số nén tối giản
- FINDCOW PTIT spoj – Find the Cow!
- P141PROC PTIT spoj – ROUND 1C – BIT operator
- P131SUMC PTIT spoj – SUM1 C – Quay bảng
- BLGEN spoj – Chuỗi gen đặc trưng
- NKNUMFRE spoj – Số thân thiện
- hướng dẫn EXPAR – spoj
- P167PROE spoj PTIT – ROUND 7E – Phương trình
http://i.imgur.com/CWCLvu8.png
admin chỉ mình cách giải bài này được ko ạ.
http://i.imgur.com/CWCLvu8.png
admin giúp mình giải bài này với ạ
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?