0.Phân tích ra thừa số nguyên tố

Submit solution
Points: 1 (partial)
Time limit: 1.0s
Memory limit: 98M
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

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ụ 1:

Input

100

Output

2 2 
5 2

Ví dụ 1:

Input

144

Output

2 4 
3 2

Comments


  • 0
    ga123  commented on Sept. 4, 2021, 1:28 p.m.

    Mình đã sửa lại code cho bạn comment bên dưới. thuật toán sàng erotos không cần thiết trong việc giải bài tập đơn giản.

    #include<stdio.h>
int main() 
{ 
long long n; 
long long dem; 
scanf("%ld", &n); 
for(long long i=2;i<=n;i++)
{
 dem=0; 
 while(n%i==0)
{
dem++;
n/=i;
}
if(dem>=1)
printf("\n%d %d",i,dem); 
}
}

  • 0
    ga123  commented on Sept. 4, 2021, 10:27 a.m.

    bài này cách làm hay nhất là kết hợp giữa thuật toán sàng kratothenes và chia dần theo số nguyên tố đã tìm được. mình sẽ update thêm code giải đáp hiệu quả hơn sau.


  • 0
    EEC_NguyenQuyTuan3  commented on Sept. 4, 2021, 10:22 a.m.

    Cho e hỏi em bị sai ở đâu vậy ạ ?

    include<stdio.h>

    int main() { int n; int dem; scanf("%ld", &n); for (int i=2;i<=n;i++){ int dem =0; while(n%i==0){ dem++; n/=i; } if(dem){ if(dem>1) printf("\n%d %d",i,dem); else printf(" \n%d ", i); if(n>1){ printf(""); } }
    }

    return 0;

    }


    • 0
      ga123  commented on Sept. 4, 2021, 11:25 a.m.

      kích thước của biến chạy từ mức 1 đến 10 mũ 9 nên bị overflow biến int, bạn phải dùng biến to hơn. nếu thay biến to hơn vào chg trình của bạn thì vẫn sẽ bị TLE time limit exceeded vì thuật toán của bạn độ phức tạp chạy quá dài. bạn thử thực hiện tách 92934234 về thừa số nguyên tố bằng thuật toán của bạn,giải tay là thấy ngay độ dài của thuật toán.


    • 0
      ga123  commented on Sept. 4, 2021, 10:32 a.m.

      mình cùng đã viết lời giải thích chi tiết trong bài toán sàng eratosthesnes, bạn có thể tự tham khảo trước


    • 0
      ga123  commented on Sept. 4, 2021, 10:30 a.m. ← edited

      {Tin nhắn đã bị xóa}


    • 0
      ga123  commented on Sept. 4, 2021, 10:28 a.m.

      bạn để toàn bộ code vào trong 3 dấu ```


  • 1
    manh_ĐTVT5_K60  commented on Sept. 25, 2020, 8:36 a.m.

    bộ test bài này có lỗi ko ạ, huhu???


    • 1
      DuyAnhhh  commented on Sept. 25, 2020, 9:21 a.m.

      Không lỗi đâu bạn ơi,tại code bạn mới chỉ phân tích được thừa số nguyên tố 2,3,5,7 thôi


      • 1
        manh_ĐTVT5_K60  commented on Oct. 8, 2020, 9:47 a.m.

        mai fen cho mình tham khảo code đc ko?