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, 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
Lưu ý trước khi xem. Code tối ưu ngắn gọn bằng java
vector 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()<
test 7 la gi vay moi nguoi
code tham khảo đây :v https://www.ideone.com/koknvZ
Sao test 1 ảo v, 102 thì phải in ra: 2 1 \n 3 1 \n 17 1 mà hình như test là: 2 2