PRIMFAC - Phân tích ra thừa số nguyên tố
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift
Cho số nguyên dương ~n~. Hãy phân tích ~n~ ra thừa số nguyên tố. Tức là tìm các số nguyên tố ~p_1, p_2, …, p_k~ đôi một phân biệt và các số nguyên dương ~α_1, α_2, …, α_k~ sao cho:$$n = {p_1}^{{\alpha _1}} \times {p_2}^{{\alpha _2}} \times ... \times {p_k}^{{\alpha _k}}$$
Input
- Gồm một dòng duy nhất chứa số nguyên dương ~n~.
Giới hạn:
- ~1 ≤ n ≤ 10^{12}~.
Output
- Dòng đầu ghi số nguyên dương ~k~
- ~k~ dòng sau, dòng thứ ~i~ ghi hai số ~p_i~ và ~α_i~ cách nhau một dấu cách, các số ~p_i~ được sắp xếp tăng dần.
Sample
Input #1
10
Output #1
2
2 1
5 1
Input #2
12
Output #2
2
2 2
3 1
Hint
- ~10 = 2^1 × 5^1~
- ~12 = 2^2 × 3^1~
Problem source: Chuyên Sơn La Online Judge
Bình luận
Test 6,8,9 là gì vậy mọi người
FULL AC CHO AE THAM KHẢO=))
Mọi người cho em xin test 1,3,10 với ạ
Lưu ý trước khi xem. Code tối ưu ngắn gọn bằng java
vector<pair> v; for(int i=2; i<=sqrt(n); i++) { int dem=0; while(n%i==0) { dem++; n/=i; } if(dem>0) { v.pushback({i,dem}); } } if(n>1) { v.pushback({n,1}); } cout<<v.size()<<endl; for(auto x:v) cout<<x.first<<" "<<x.second<<endl;</pair>
test 7 la gi vay moi nguoi
n = 1
code tham khảo đây :v https://www.ideone.com/koknvZ
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.