Tính giai thừa n (n!) theo số nguyên tố

[phamtuanic]

Cho một số nguyên dương N<=1000.Hãy tìm biểu diễn số N! dưới dạng số lần xuất hiện các số nguyên tố trong phân tích số N! ra thừa số nguyên tố
Ví dụ :
INPUT
10
OUTPUT
8 4 2 1

[Xcross87]

N <= 1000 chọn N = 100 => N! = ???

[whoru]

"N <= 1000 chọn N = 100 => N! = ???" <- có lẽ bạn đã hiểu lầm ý cùa phamtuanic. Ở đây, đâu nhất thiết phải tính ra N!, chỉ cần phân tích số N! thành các số nguyên tố thôi
Theo mình thấy đây là vấn đề ko khó, có thể giải như sau:
Xét 1 số nguyên dương k >=3.
+ Dùng 1 mảng để chứa các số nguyên tố < k ( ko kể 1 ) và 1 mảng thứ 2 tương ứng với mảng 1 để chứa số lần xuất hiện của các số nguyên tố này trong N! ( chẳng hạn N = 10 như trên thì mảng 2 chứa các số 8, 4, 2, 1 để sau đó xuất ra )
+ Lúc đầu mảng 2 = { 0 }.
+ Gán mang1[ 0 ] = 2 và mang1[0] = 1; // số nguyên tố đầu tiên
- Ta phân tích k ra các thừa số nguyên tố bằng cách lần lượt kiểm tra k% mang1[ i ], nếu chia hết thì tăng mang2[ i ] thêm 1 và lấy thương của phép chia làm tiếp.
- Nếu k là nguyên tố thì mang1[ số phần tử ++ ] = k và trong mang2 tương ứng là 1 ( chẳng qua là ta thêm số nguyên tố k này vào mang1 và mang2 )

Từ giải thuật trên, cứ duyệt từ 3 -> N là xong. Chú ý, khi ta tăng k lên, ta phải xóa hết mang2 thành 0.
Ở đây mình làm theo kiểu "cuốn chiếu" tức là đồng thời xét k và xem k có nguyên tố ko để còn thêm nó vào 2 mảng. Hoặc bạn cũng có thể tìm tất cả các số nguyên tố < N rồi sau đó mới đi phân tích từng thừa số trong N!
Hi vọng ý kiến cùa mình có thể giúp bạn. Thân!

[phamtuanic]

thanks!!đã góp ý