PRIMFAC - Phân tích ra thừa số nguyên tố

View as PDF
Submit solution
Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 256M
Author:
Hieu Nguyen
Problem type
Allowed languages
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

Comments

Please read the guidelines before commenting.


  • 0
    rank  commented on Dec. 18, 2024, 1:20 p.m.

    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()<


  • 0
    MEOWMEOW  commented on Oct. 9, 2024, 2:32 p.m.

    test 7 la gi vay moi nguoi


  • 0
    Aothatday  commented on Jan. 17, 2024, 2:39 p.m.

    code tham khảo đây :v https://www.ideone.com/koknvZ


  • 0
    vdtue  commented on Sept. 13, 2023, 1:38 p.m.

    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