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

#1

Giúp em bài này với!!!
Phân tích N! ra thừa số nguyên tố. (số N có thể lớn hoặc rất lớn )
N! =2^x2 * 3^x3 … p^xp *…
Với N,p nhập từ bàn phím. (p là số nguyên tố).
Xuất ra màn hình: xp. (xp là số lần xuất hiện của p)
VD: N=4, p=2
4! = 2^3 * 3^1
==> xp = 3

Đây là code tính giai thừa em mò mẫm đc, còn phần tìm ra xp thì em chịu.

int i, j, n, so;
	unsigned long sl;
	unsigned sn;
	int a[MAX];

	printf("Chuong trinh tinh giai thua so lon.\n Nhap n: ");
	scanf_s("%d", &n);
	a[0] = 1;
	sn = 0;
	so = 1;

	for (i = 1; i <= n; ++i)
	{
		sn = 0l;
		for (j = 0; j<so; ++j)
		{
			sl = i*a[j] + sn;
			a[j] = sl % 10000;
			sn = sl / 10000;
		}
		if (sn)
			a[so++] = sn;
	}

	for (j = so - 1; j >= 0; j--)
		printf("%d", a[j]);
	printf("\n");
1 Like
#2

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

#3

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

#4

Bách Khoa TPHCM à b :))

#5

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

#6

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 :smiley:

#7

:smiley: 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 :smile:

1 Like
#8

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:


2 Likes
#9

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)
= (21)(31)(22)(51)(21 31)(71)(23)(32)(21 51)
= 21+2+1+3+1 31+1+2 51+1 71
= 28 34 52 71

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

4 Likes
#10

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

#11

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

#12

  • 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ỉ :neutral_face:

3 Likes
#13

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

Bài này 1 for :smiley: 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 :smiley:
  • 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.
1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?