Xin góp ý thuật toán: phân tích một số nguyên N thành tích của các thừa số nguyên tố

tcm · July 26, 2016, 2:38am

Nhờ mọi người cải tiện thuật toán của mình hoặc sáng tạo ra thuật toán mới của bài này

Xin chào mọi người. Nhờ mọi người giúp mình !

Đề bài: Viết chương trình phân tích một số nguyên N thành tích của các thừa số nguyên tố.
VD: 18 = 2 * 3 * 3

Đây là code của mình:

bool KiemTra(int n)
{
	if (n == 2)
		return true;
	if (n % 2 == 0)
		return false;
	for (int i = 3; i <= sqrt(n); i += 2)
	{
		if (n % i == 0)
			return false;
	}
	return true;
}
void PhanTich(int n)
{
	for (int i = 2; i <= n; i++)
	{
		for (int j = i;;)
		{
			if (n % j == 0 && KiemTra(j))
			{
				cout << j << " * ";
				n /= j;
			}
			else
				break;
		}
	}
}
int main()
{
MINH:
	int n;
	do
	{
		cout << endl << "\nNhap vao so can phan tich: ";
		cin >> n;
		if (n < 2)
			cout << "\nSo n khong hop le\n";
	} while (n < 2);
	PhanTich(n);
	goto MINH;
	getch();
	return 0;
}

Tuy nhiên nhìn đoạn code trên, ai cũng thấy Thuật toán của mình khá “ngoằn ngoèo” và luôn dư 1 dấu * ở cuối nên nhờ mọi người cải thiện giúp mình Thuật toán giải bài này, nếu không thì xin Thuật toán của mọi người mà hay hơn, mình sẽ tham khảo.
Cảm ơn rất nhiều

tntxtnt · July 26, 2016, 1:47am

if (n % j == 0 && KiemTra(j))
ko cần phải kiểm tra xem j có phải là số nguyên tố nữa đâu. Vì sao thì do magic nhé

void PhanTich(int n)
{
	for (int i = 2; i <= n; i++)
	{
		for (int j = i;;)
		{
			if (n % j == 0)
			{
				cout << j << " * ";
				n /= j;
			}
			else
				break;
		}
	}
}

1 hàm PhanTich là đủ rồi, bỏ luôn hàm KiemTra đi. Nên đặt tên hàm rõ hơn. KiemTra là kiểm tra cái gì? Nếu ktra là só ng tố thì đặt tên hàm rõ ràng ra là LaSoNguyenTo. Nếu dài quá thì xài tiếng Anh: isprime

vòng for (int j = i; ... kia cũng thừa thãi. Viết thế này là đủ rồi:

void PhanTich(int n)
{
    for (int i = 2; i <= n; i++)
        for (; n % i == 0; n /= i)
            cout << i << " * ";
}

tcm · July 26, 2016, 1:58am

Magic tuyệt và ảo thật, không bao giờ ra hợp số, anh @tntxtnt giải thích sơ cho em với

Ok anh, em sẽ chú ý (do lười quá)

Ông nội … của tuyệt vời

Anyway, còn chỗ nào nữa không anh nhỉ , cái lỗi dư 1 dấu * ở cuối em vẫn chưa khắc phục được

tntxtnt · July 26, 2016, 2:20am

magic là do vòng for ở trong. Nó luôn chia n/=i tới khi nào n ko chia hết cho i nữa. Như vậy n cung ko chia hết cho bội của i luôn.

ví dụ n/=2 tới khi n ko chia 2 được nữa, thì n sau đó sẽ ko chia hết cho 4, 6, 8, 10, v.v… được nữa luôn. Vì vậy nếu n%i == 0 thì i chắc chắn là số nguyên tố, vì nếu là hợp số i = a*b, a, b < i, thì trước đó đã có n/=a với n/=b hết rồi.

bỏ cái dấu * cuối thì gây ra code hơi xấu Cách đẹp nhất là tạo thêm 1 biến count để đếm số lượng thừa số ngto đã được in ra. Nếu count == 0 thì đừng xuất *, nếu count != 0 thì xuất * trước khi xuất i.

void PhanTich(int n)
{
    for (int i = 2, count = 0; i <= n; i++)
        for (; n % i == 0; n /= i)
            cout << (count++ ? " * " : "") << i;
}

tcm · July 26, 2016, 2:24am

Toán tử 3 ngôi hả anh ? Cái về bên trái ấy, nó viết tắt của dạng count > 0 ? " * " : " " đúng không anh ?

Em vẫn chưa hình dung được lắm

tcm · July 26, 2016, 2:28am

Mà sao lúc em ghi

nó không ra anh nhỉ, em tưởng cái này với cái anh nói nó giống nhau

tntxtnt · July 26, 2016, 2:30am

đúng rồi, nó viết tắt của

if (count > 0) cout << " * ";
cout << i;
count++;

viết gọn lại nhờ ? :, nhưng cần có trường hợp cho count==0: bỏ cái chuỗi rỗng "" vào.

cần phải tăng biến đếm count nữa, vì mình cout kiểu * i, dấu nhân nằm trước, như vậy chỉ có thừa số ban đầu ko có dấu *, mấy số sau thì cần, bởi vậy mới tăng biến count để biến mấy biến sau cần phải xuất *

tcm · July 26, 2016, 2:30am

À hiểu rồi, count không ++ nên mãi = 0

Sao không có cặp dấu ngoặc tròn () là nó báo chuỗi rỗng bị lỗi anh ?

tntxtnt · July 26, 2016, 2:37am

tại toán tử <<. Có thể nó hiểu là
((cout << count++) ? " * " : "") << i;
cụm
((cout << count++) ? " * " : "") sẽ là chuỗi " * " hoặc "", thì ko có toán tử " * " << i, gây ra lỗi

tntxtnt · July 26, 2016, 2:39am

vậy chưa xong đâu, có cách “cải tiến” mới, vừa nhanh hơn mà cũng chả cần biến count bỏ dấu * sau cùng:

void PhanTich(int n)
{
    for (int i = 2; i <= sqrt(n); i++)
        for (; n % i == 0; n /= i)
            cout << i << " * ";
    cout << n;
}

i chỉ cần chạy tới căn(n) là đủ, ko cần chạy tới n. Viết thế này thì nếu n là số nguyên tố lớn, ví dụ 2^31 - 1 hay 2147483647 thì i chỉ cần chạy tới 2^16 là dừng, lẹ hơn rất nhiều. Trick ở đây là thừa số cuối cùng sẽ ko được in ra. Nhưng mà thế này hơi bị khỏe: thêm cout << n; là được. Vui vẻ cả làng vừa in ra đủ thừa số nguyên tố, vừa loại bỏ được dấu * cuối cùng.

nếu viết như trên thì cũng tạm ổn rồi, nhưng cách này cũng có nhược điểm: mỗi lần ktra `i <= sqrt(n)` lại phải đi lấy căn(n). Làm vậy ko được lẹ cho lắm. Ta cần thêm 1 biến phụ nữa: `r` ``` void PhanTich(int n) { for (int i = 2, r = sqrt(n); i <= r; i++) { if (n % i == 0) { for (; n % i == 0; n /= i) cout << i << " * "; r = sqrt(n); //chỉ tính lại căn n khi n thay đổi } } cout << n; } ``` dài hơn, nhưng ổn hơn là trông cậy vào compiler tối ưu dùm

tcm · July 26, 2016, 2:45am

Wonderful

Ok anh để em xem xét và nghiền ngẫm kỹ lại

tntxtnt · July 26, 2016, 2:44am

cái magic kia thì chịu chấp nhận đi, nó hơi khó giải thích nên anh mới nói là magic

thinguyen_92 · October 10, 2017, 7:54am

Các bác cho em xin ý tưởng để viết chương trình với.

rogp10 · October 10, 2017, 10:12am

Vậy bạn không rút ra được gì sau khi đọc nửa topic về sau chăng?

rogp10 · April 10, 2018, 11:14am

Nếu thừa số cuối cùng là bình phương trở lên thì sẽ dư dấu *.

Còn vì sao khi n % i == 0 thì i chắc chắn nguyên tố?

Vòng lặp trong đảm bảo rằng j ∤ n , ∀j \ 1 < j < i
Mà i | n => j ∤ i, ∀j \ 1 < j < i, đây là đn nguyên tố

Nếu j chia hết i thì j cũng chia hết n nên j không chia hết n thì j cũng không chia hết i luôn, vậy j nguyên tố.

tntxtnt · November 28, 2017, 1:34pm

ờm, bị dư dấu * nhưng do cout << n cuối cùng thành ra dư * 1 @_@

void PhanTich(int n)
{
    int count = 0;
    for (int i = 2, r = sqrt(n); i <= r; i++)
        for (; n % i == 0; n /= i)
            cout << (count++ ? " * " : "") << i;
    if (n != 1)
        cout << (count++ ? " * " : "") << n;
}

hơi sấu @_@

p.lien198 · April 10, 2018, 10:46am

#include <stdio.h>
#include <math.h>

int main() {
int n, i=2;
scanf("%d", &n);
// int a = n;
// int x = sqrt(n);

	while ( n>=i   )
   {
   
	int dem = 0;
    while(n % i == 0) {
        dem++;
        n /= i;
    }
    if(dem!=0)
    printf("%d %d\n",i,dem);
	i++;	
   }

}

có thuật toán nào tối ưu hơn k ạ? nộp lên SPOJ toàn báo chạy quá thời gian

rogp10 · April 10, 2018, 6:01pm

Vậy là bạn chưa đọc topic này code bạn chạy tới n chứ chưa dùng cận sqrt(n).

p/s: đã sửa lại post trên chút cho nó có logic.

Có thể phân tích code như sau:

Bất biến: n là số nguyên dương và 2 < i <= sqrt(n).
Điều kiện trước lặp (pre-cond): i <= sqrt(n) và n không chia hết cho j với 2 < j < i.
Nếu i chia hết n thì vòng lặp bên trong sẽ chạy cho đến khi n không chia hết cho i nữa.
Vậy điều kiện pre-cond được duy trì.
n không chia hết cho j => i cũng không chia hết cho j => i nguyên tố vì đảo lại, nếu i chia hết cho j thì n cũng phải chia hết cho j chứ.

p.lien198 · April 10, 2018, 5:46pm

Thế thì thành kiểm tra số nguyên tố r. Nếu cho chậy đến sqrt (n) thôi. Thì những số ngto như 5 7 9 làm sao nó in ra đc?

rogp10 · April 10, 2018, 6:02pm

Mấy bài mình viết trong topic này là dựa trên code @tntxtnt đã viết rồi mà 9 có nguyên tố đâu nhỉ.