Phân tích 1 số thành các số nguyên tố

[rox_rook]

Mình đưa ra bài này vì lâu rồi không thấy mọi người cùng làm chung bài tập. Để tạo lại bầu không khí khi xưa vậy. Bài này không khó, và cũng có rất nhiều cách làm. Ai làm được cứ post, không làm được đưa ý tưởng cũng very welcome. T_T ! ( Đừng chê dễ quá không thèm làm là được rùi )
Đề bài yêu như sau yêu cầu user nhập vào 1 số, phân tích ra thừa số nguyên tố, vậy thui.

Input and Output

Enter number: 36

Prime factors: 2 x 2 x 3 x 3

[huynguyen]

Ý tưởng:
Nhập n
Cho i chạy từ 2 đến sqrt(n), nếu gặp 1 số là số nguyên tố thì lấy n chia nguyên nó cho đến khi ko chia được nữa thì lại tiếp tục. Quá trình tiến hành cho đến khi n=1, mỗi lần chia nguyên được thì kết xuất ra màn hình con số nguyên tố đó và dấu x.
Sẽ có code sau nếu vẫn chưa ai hiểu ^^

[rox_rook]

Yeah ! Bravo ! Ý tưởng ông đúng rùi T_T ! Post code cho mọi người tham khảo đê chứ hì hì ! Thật ra mấy cái này cũng mẹo 1 tí thôi, cũng còn nhiều cách, để chờ mọi người post lời giải nhiều nhiều rùi tui post mấy cách khác lên T_T! Còn bác nào nữa không nhỉ ? ~~

[huybka]

mình viết=C ,test qua thì thấy đúng,mọi người góp ý nhé

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

int isprime(int n)
{
	int i;
	for(i=2;i<=sqrt(n);i++)
	 if(n%i==0)return i;
        return 0;
}

main()
{
	int n,i,p[50],count=0;
	printf("\ninput: ");scanf("%d",&n);
	while(n>1)
	{
		if(!isprime(n)){p[count++]=n;break;}
		else {
			p[count++]=isprime(n);
			n=n/(isprime(n));}
	}
	for(i=0;i<count;i++)
	printf(" %d ",p[i]);


}

[rox_rook]

Thuật toán chính xác, code viết rất dễ hiểu ! Cái này ý tưởng chắc cũng na na giống huynguyen nhỉ ? Thanks bài làm của bạn nhé ^^!

[huybka]

uhm nhưng mình nghĩ cách này hơi thô,đợi mai thi xong tối về nghĩ xem có cách nào hay không

[sieuphuong]

Ý tưởng:
Nhập n
Cho i chạy từ 2 đến sqrt(n), nếu gặp 1 số là số nguyên tố thì lấy n chia nguyên nó cho đến khi ko chia được nữa thì lại tiếp tục. Quá trình tiến hành cho đến khi n=1, mỗi lần chia nguyên được thì kết xuất ra màn hình con số nguyên tố đó và dấu x.
Sẽ có code sau nếu vẫn chưa ai hiểu ^^

Em ko hiểu tại sao chỉ chạy đến căn bậc 2 của n ???

[Kevin Hoang]

Em ko hiểu tại sao chỉ chạy đến căn bậc 2 của n ???

Nếu là bài: Tìm các số nguyên tố từ 1 đến n thì bạn sẽ tìm các số đó trong khoảng nào? [1;sqrt(n)] hay là [1;n]?

[sieuphuong]

Nếu là bài: Tìm các số nguyên tố từ 1 đến n thì bạn sẽ tìm các số đó trong khoảng nào? [1;sqrt(n)] hay là [1;n]?

Em ví dụ tìm các số nguyên tố từ 1 đến 100 thì em sẽ tìm từ 1 đến 100 chứ sao chỉ tìm từ 1 đến căn của 100 = 10 .

[Kevin Hoang]

Em ví dụ tìm các số nguyên tố từ 1 đến 100 thì em sẽ tìm từ 1 đến 100 chứ sao chỉ tìm từ 1 đến căn của 100 = 10 .

Toán học đã chứng minh được rằng. Các số nguyên tố nhỏ hơn một số nguyên n nằm trong khoảng nhỏ hơn sqrt(n).