Code phân tích N thành thừa số nguyên tố bị sai kết quả

Đề bài yêu cầu nhập số nguyên, sau đó phân tích thành thừa số nguyên tố. ví dụ nhập 100 sẽ in ra 2 2 5 5. Cho em hỏi bài của em sai ở bước nào mà nó chạy ra kết quả lỗi ạ. Ai góp ý giùm em với.

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

void print(int n);
int check_SNT(int x);

int main()
{
	int n;
	do
	{
		printf("Nhap so nguyen duong n: ");
		scanf_s("%i", &n);
	} while (n < 1);
	print(n);
	return 0;
}

void print(int n)
{
	if (n == 1)
		printf("\n"); 
	else for (int i = 2; i <= n; i++)
		if (n%i == 0) if (check_SNT(i))
		{
			printf("%i ", i);
			print(n / i);
		}
}

int check_SNT(int x)
{
	int check = 1;
	for (int i = 2; i <= sqrt(x); i++)
		if (x%i == 0) check = 0;
	return check;
}

Lỗi sai như thế nào vậy bạn?

Ví dụ nhập 10 nó sẽ xuất ra
2 5
5 2
Nhập 6 thì xuất ra
2 3
3 2
Mà nhập 4 hay 9 thì ra đúng đáp án

Thực ra không cần phải “check” lại đâu :slight_smile: cứ chia cho đến không còn thừa số đó thì nghiễm nhiên những số chia hết sẽ toàn là nguyên tố.

2 Likes

25 với 52 khác gì nhau?
23 với 32 khác gì nhau?

Bạn cho tất cả kết quả vào 1 array, rồi bạn viết ngược lại là đúng thôi chứ có gì đâu.

Ý tưởng của bạn là gì?

Dễ thấy code này không hề làm gì với n nên chỉ đúng với số square-free.

Mình tìm số nguyên tố nhỏ nhất có thể chia hết cho n sau đó in số đó ra, rồi lại tiếp tục hàm đó với n=n/i, đến khi chia đến n=1 thì dừng đệ quy

Không bạn ơi, chương trình xuất kết quả cả 2 đáp á là 2 5
5 2 luôn. Nên mình mới bảo sai đấy bạn.

Bạn đệ quy chỗ này làm gì, trong khi bạn chỉ cần n /= i.

Em tìm kiếm trên diễn đàn cũng có nhiều bài như này rồi nhé.

for(i=2;i<=n;i++){
        while(n%i==0){
            if(n==i) std::cout<<i;
            else std::cout<<i<<" * ";
            n=n/i;
        }
}
1 Like

à tại em đang học phần đệ qui nên muốn làm đệ quy ấy mà anh.

nếu không có hệ thức đệ quy thì chương trình sẽ bỏ qua số nguyên tố vừa chia xong, có thể nó sẽ được chia lại lần nữa nên nếu bỏ qua sẽ sai.

Ai bảo thế? Bạn đã in ra i rồi, bạn chia i rồi, làm sao mà bỏ qua số nguyên tố vừa chia được?

có thể chia lại lần nữa. ví dụ số 4 = 2*2 sẽ in ra 2 2. làm như bạn chỉ có số 2 thôi :))

Rách việc nhỉ.

if (i thoả mãn) {
    while (n % i == 0) {
        printf("%d ", i);
        n /= i;
    }
}

yêu cầu của đề là viết đệ quy mà bạn

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

void print(int n);

int main()
{
int n;
do
{
printf(“Nhap so nguyen duong n: “);
scanf_s(”%i”, &n);
} while (n < 1);
print(n);
system(“pause”);
return 0;
}

void print(int n)
{
int i;
if (n == 1)
printf("\n");
else
{
for (i = 2; i <= n; i++)
if (n%i == 0)
{
printf("%i ", i);
break;
}
print(n / i);
}
}

bạn có thể mình sửa thê này, thứ nhất là không cần hàm check, thứ hai là đừng bỏ đệ quy vào trong vòng lặp kể cả có break; đi nữa,

Hàm check thừa mình k giải thích, vấn đề đệ quy giống như gọi hàm trong hàm, vì bạn bỏ vào vòng lặp, giả sử bạn nhập 100, trong vòng lặp for đầu tiên nó tìm ra 2, sau đó nó gọi hàm và tìm tiếp đến khi trờ về 1( 100/i/i/i ==1), nó thoát và lại bắt đầu vòng lặp for với giá trị n=100, bắt đầu từ i=3, nó lại tìm ra 5 và bắt đầu tiếp, vòng lặp đó làm đệ quy của bạn chạy trùng

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?