Chủ đề này có 7 trả lời

[pntruongan]

Cái phân tích số thành thừa số này học từ dời tám hoánh nào đó lúc cấp 2.
Nhưng sau này chẳng đụng tới nữa, chỉ được cái em thấy nó đơn giản nên lôi ra để tập xây dựng thuật toán.
các bác xem hộ thuật toán này tối ưu chưa nhỉ

void phantich2 (int so ) {
	int k&#59;
	while ( so != 2 ) {
  int can2 = int(sqrt (so));
  for &#40;k=2&#59; k<= can2; k++&#41; {
 	 if &#40;so % k ==0&#41; { 
    cout << k << &#34;, &#34;&#59;
    so=so/k; k=2;
    break&#59; 
 	 } 
  }
  if &#40;k>can2 &#41;{ //khi pha^n ti&#39;ch nha^&#96;m so^&#39; nguye^n to^&#39;
 	 cout << so << &#34;, &#34;&#59; break&#59; 
  }
	}
}

[toilachinhtoi]

Thuật toán tốt nhất là của Manindra năm 2004.
http://www.cse.iitk....rimality_v6.pdf

[kakalot]

void phantich2 (int so ) {
int k;
while ( so != 2 ) {
int can2 = int(sqrt (so));
for (k=2; k<= can2; k++) {
if (so % k ==0) {
cout << k << ", ";
so=so/k; k=2;
break;
}
}
if (k>can2 ){ //khi pha^n ti'ch nha^`m so^' nguye^n to^'
cout << so << ", "; break;
}
}
}

Thuật toán này chỉ để làm cho biết chứ hiệu quả không cao, khi số chữ số của n lớn vượt quá cỡ từ của máy nó chịu, với lại lệnh "so=so/k; k++" cực kì mất thời gian.

Bài viết đã được chỉnh sửa nội dung bởi kakalot: 18-05-2006 - 10:13

[TheIncredibleMachine]

Thực thao tác đó cũng không chậm lắm, nhất là với bài toán phân tích một số ra thừa số nguyên tố thông thường

[pntruongan]

Thuật toán tốt nhất là của Manindra năm 2004.
http://www.cse.iitk....rimality_v6.pdf

Đọc cái tài liệu này khó hiểu quá, chỗ nào nó dùng chữ thì còn hiểu bặp bẹ, chứ còn nêu nó chơi ký hiệu thì chịu thôi.
Nhưng mà hình như đây là thuật toán nhận dạng mốt số có phải là số nguyên tố hay không.
Vậy làm sao đẻ phân tích môt số thành số nguyên tố, hình như không có đề cập đên

[classpad300]

Thực chất vấn đề nhận dạng 1 số có phải là số nguyên tố hay không cũng chính là phân tích số đó thành tích các thừa số nguyên tố. Nếu không phân tích được thì nó là SNT.

[jason voorhees]

Đệ mới vừa kết thúc môn C xong ,không biết thuật toán như vầy có tối ưu chưa , có gì xin mấy huynh chỉ giáo

---------------------------------------------
#include<stdio.h>
#include<conio.h>
void main()
{
clrscr();
int i,j,m;
scanf("%d",&j);
for (m=2;m<=j;m++)
{
i=0;
while ((j%m)==0)
{
i++;
j=j/m;
}
if (i!=0) printf("%3d\t%d\n",m,i);
}
getch();
}

[pntruongan]

viết chả thụt đầu dòng gì cả, khó đọc quá.
CHỉ thấy chỗ này:
i++;
j=j/m;
thế này thì i!=0 luôn luôn đúng rồi, biến i đóng vai trò gì ở đây?