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ố

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 << " * ";
}

Vì sao thì do magic nhé

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

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

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

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

Ô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

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;
}

count++ ? " * " : ""

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 ?

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.

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

Mà sao lúc em ghi

count > 0 ? " * " : " "

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

đú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 *

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

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

bỏ cái chuỗi rỗng “” vào.

cout << (count++ ? " * " : "") << i;

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

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

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

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.

Wonderful

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

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

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

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

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

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

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ố.

ờ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 @_@

#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

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ứ.

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?

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ỉ.