Phân tích n! thành thừa số nguyên tố

Nếu chỉ cần đếm xp thì có một công thức tính như sau f(n,p)= f(n/p,p)*p +n/p. Công thức này bạn có thể tìm hiểu về bài toán đếm số 0 tận cùng của n! trong hệ cơ số p.
Còn phân tích toàn bộ ra thừa số nguyên tố thì bạn nên dùng sàng nguyên tố nó sẽ giúp làm nhanh hơn

Cảm ơn bạn. Bạn có thể giải thích công thức đấy rõ hơn đc k?

Bách Khoa TPHCM à b :))

Bách Khoa TPHCM à b :))

Đề của bên đấy á bạn :))) thấy hay hay nên làm thử

thằng bạn cùng phòng cũng hỏi mình mà thấy 999.999.999! nên đang ngán

mình hỏi đc phương pháp rồi và tối nay đang định chiến thử với nó lại

Bài tập kiểu này bạn có thể tìm trên projecteuler.net. Theo mình không nên tính giai thừa rồi lại chia ra thừa số nguyên tố, vì làm vậy có thể làm tràn bộ nhớ trong bước tính giai thừa.

Thay vào đó, nên phân tích từng thừa số trong giai thừa ra thừa số nguyên tố trước. Rồi cộng bậc của tất cả các thừa số nguyên tố lại

Một số tự nhiên bất kì chỉ có đúng một tổ hợp thừa số nguyên tố. Cách phân tích 1 số K ra thừa số nguyên tố. Bạn có thể tham khảo thuật toán bên dưới. Cách này dựa theo phương pháp “Sàng Erathosthenes”:

k = 2354353454;
for (int i = 2; i*i <= k; i++) {
    if (k % i== 0) {
       k /=i; 
       i--;
    }
}

Bạn có thể đọc thêm ở đây:

Prime number

A prime number (or a prime) is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways of writing it as a product, 1 × 5 or 5 × 1, involve 5 itself. However, 6 is composite because it is the product of two numbers (2 × 3) that are both smaller than 6. Primes are central in number theory because of the fundamental theorem of arit...

Sàng Eratosthenes

Sàng Eratosthenes là một thuật giải toán cổ xưa để tìm các số nguyên tố nhỏ hơn 100. Thuật toán này do nhà toán học cổ Hy Lạp là Eratosthenes (Ơ-ra-tô-xten) "phát minh" ra. Ban đầu, nhà toán học Eratosthenes sau khi tìm ra thuật toán, đã lấy lá cọ và ghi tất cả các số từ 2 cho đến 100. Ông đã chọc thủng các hợp số và giữ nguyên các số nguyên tố. Bảng số nguyên tố còn lại trông rất giống một cái sàng. Do đó, nó có tên là sàng Eratosthenes.[cần dẫn nguồn] Để tìm các số nguyên tố nhỏ hơn hoặc bằng...

phân tích giai thừa của từng số từ 2 tới n, rồi cộng số mũ tương ứng của các thừa số nguyên tố đó lại

ví dụ:
10! = 1.2.3.4.5.6.7.8.9.10
= 2.3.4.5.6.7.8.9.10 (bỏ qua số 1 vì nó ko có thừa số nguyên tố nào)
= (2¹)(3¹)(2²)(5¹)(2¹ 3¹)(7¹)(2³)(3²)(2¹ 5¹)
= 2^1+2+1+3+1 3¹⁺¹⁺² 5¹⁺¹ 7¹
= 2⁸ 3⁴ 5² 7¹

nếu chỉ tính số mũ của 1 thừa số nguyên tố nhất định thì còn dễ hơn nữa. Ko cần phân tích m (1 < m <= n) thành thừa số nguyên tố mà chỉ cần phân tích m = pq k và bỏ qua k

Cảm ơn bạn @tntxtnt và bạn @Tobi đã chỉ cho mình phương pháp hay để mình làm lại thử với cách của hai bạn.

tính giai thừa số lớn thì dùng xâu, giả sử tính 1000 giai thừa thì mảng k thể chứa hết được => nên bắt buộc dùng xâu

• Có cách cài bignum dùng mảng.

• 1000! có 2568 chữ số, nếu như bạn cài bignum bằng string thì độ phức tạp là O(n * log(n!)). n = 1000 thì tính ngót nghét 2 triệu phép tính, rồi lại phân tích ra thừa số nguyên tố, có lẽ hơi căng.

• Bài toán là phân tích giai thừa thành thừa số nguyên tố, sao bạn không làm cách khôn ngoan hơn là phân tích từng số trong giai thừa thành thừa số nguyên tố rồi cộng các số mũ lại?

P/s: Bạn có vẻ thích đào mộ nhỉ

Đề bài không yêu cầu tính n! đâu thớt đang quáng thôi.

Bài này 1 for và giải thích như sau:

• Để trích lấy thừa số p ứng với n, ta liên tục chia n cho p cho đến khi dư.
• Trải ra từ 1 đến n, có n DIV p số chia hết cho p. Ta có n DIV p * p + r = n (r >= 0), nên liệt kê được: 1p, 2p, …, n DIV p
• Tương tự, có n DIV p^2 số chia hết cho p^2. Mà n DIV p DIV p = n DIV p^2, nên 1 for thôi.