huynguyen 02-02-2007, 12:47 AM Bài toán này đã trở nên rất đỗi quen thuộc với chúng ta, trong bài này chúng ta sẽ bàn đến cách kiểm tra 1 số nguyên N cho trước có nguyên tố hay không trong phạm vi kiến thức số học sơ cấp.
Có rất nhiều cách, các cách thông thường là:
+ Xét các số từ 1 đến N xem có bao nhiêu số là ước của N rồi so sánh với 2. Cách này chạy rất chậm!
+ Xét các số từ 2 đến sqrt(N) rồi nếu là ước của N thì dừng lại, nhanh hơn 1 chút!
Ta sẽ bàn 1 cách nhanh hơn nữa:
Rõ ràng cái ta cần là làm sao giảm bớt số lượng số phải đem ra thử có phải là ước của N hay không. Trong danh sách này, có thể thừa (như 2 cách trên thừa rất nhiều) nhưng tuyệt đối không được thiếu các số nguyên tố bé hơn hoặc bằng sqrt(N). Vậy thì ta sẽ duyệt các số này theo 1 quy luật nào đó. Quy luật đó là gì?
Nhận xét: 1 số nguyên tố chia cho 6 dư 1 hoặc 5 (dễ dàng chứng minh) suy ra tập các số nguyên chia 6 dư 1 hoặc 5 sẽ bao trùm tập các số nguyên tố.
Từ đây ta có thuật toán: ta chỉ xét các số bé hơn hoặc bằng sqrt(N) mà chia 6 dư 1 hoặc 5 mà thôi, nếu N chia hết cho bất cứ 1 số nào trong đó thì N là hợp số, trái lại N là nguyên tố.
không phải ngẩu nhiên mà tôi chọn hằng số k= 6 này. Bài toán trở thành tìm số k mà từ 1 tới k-1 có ít số nguyên tố cùng nhau với nó nhất. Khi đó tỉ lệ phải xét chính là tỉ số các số nguyên tố cùng nhau này với k
thực nghiệm thì thấy số k tổng quát là tích của vài số nguyên tố đầu tiên, tất nhiên càng nhiều thì tỉ lệ phải xét càng nhỏ nhưng cài đặt có phần phức tạp hơn
các bạn mới làm toán thì bỏ qua tìm số k này, giỏi lên một tí các bạn cho k=2 để loại các số chẳn
rồi k=6 để loại các số chia hai huặc ba
nếu k=2*3*5=30( tỉ lệ phải xét, 4/15) thì tốc độ đc cải thiện đáng để, bạn thử cài đặt nhé, chú ý cái đặt thế nào cho thông minh
khi nghịch mã nguồn của Maple thì thấy nó lấy k là tích các số nguyên tố <1000 cơ blackpawn 16-02-2008, 09:39 AM Số là số chia hết cho chính nó và 1 vì thế nên ta có thể ko xét 1 mà chỉ xét từ sqrt của nó đến nó.Làm cách này tuy nó hơi khó hiểu chút nhưng rất nhanh đấy,cách này Thầy mình đã chấp nhận
Ủa, sao không xét từ 2 đến sqrt(n), như vậy có lẽ nhanh hơn
các bạn mới làm toán thì bỏ qua tìm số k này, giỏi lên một tí các bạn cho k=2 để loại các số chẳn
rồi k=6 để loại các số chia hai huặc ba
nếu k=2*3*5=30( tỉ lệ phải xét, 4/15) thì tốc độ đc cải thiện đáng để, bạn thử cài đặt nhé, chú ý cái đặt thế nào cho thông minh
khi nghịch mã nguồn của Maple thì thấy nó lấy k là tích các số nguyên tố <1000 cơ
Theo em hiểu thì khi xét số chia dạng mk + r < sqrt(n), ta sẽ bỏ không xét các số có USCLN(r, k) > 1 phải không ạ? Nếu tính trước thì chắc là nhanh, nhưng nếu đến lúc chạy mới xét thì chắc tốc độ cũng giảm đáng kể.
Có phải Maple dùng cách lưu sẵn các số này không ạ?(:-)? QuangHoang 29-09-2008, 09:50 AM Tôi thấy cách làm này chỉ đúng với các số nguyên tố từ 19 trở lại thôi, nhưng 2, 3 thi sao nhi???? . Rõ ràng cách làm này không ổn lắm.
Sao lại chỉ đúng với 19 trở lại vậy bạn?
Ta sẽ bắt đầu xét từ 5, để 2,3 là các trường hợp riêng, thuật toán này rất hay đấy chứ. Nó giúp loại bớt số lần tính toán.
Bài này mình đã code thử, bạn tham khảo xem sao:
/*
- Mot so nguyen to chia 6 du 1 hoac 5. Dieu do co nghia la bao trum len cac so nguyen to
la cac so chia het cho 1 va 5.(tru 2 va 3)
- So chan khong phai la so nguyen to
Day la bai toan tim cac so nguyen to tu 1 den n
*/
#include <stdio.h>
#include <math.h>
int ktnt(int n);
main()
{
int n,i;
printf("Please, enter an integer number ( n>=5 ): ");scanf("%d",&n);
if (n<2)return 0;
else if (n<4)
for(i=2;i<=n;i++)
printf("%4d",i);
else
{
printf(" 2 3");
for (i=5;i<=n;i+=2)
if ((i % 6 == 1 || i % 6 == 5) && ktnt(i))
printf("%4d",i);
}
}
int ktnt(int n) //Ham ktnt nay khong chuan muc voi nhieu bai
{
int i;
for (i=3;i<=sqrt(n);i++)
if (n%i==0) return 0;
return 1;
} thongnlkh_aptech 21-01-2009, 12:26 AM Sao lại chỉ đúng với 19 trở lại vậy bạn?
Ta sẽ bắt đầu xét từ 5, để 2,3 là các trường hợp riêng, thuật toán này rất hay đấy chứ. Nó giúp loại bớt số lần tính toán.
Bài này mình đã code thử, bạn tham khảo xem sao:
/*
- Mot so nguyen to chia 6 du 1 hoac 5. Dieu do co nghia la bao trum len cac so nguyen to
la cac so chia het cho 1 va 5.(tru 2 va 3)
- So chan khong phai la so nguyen to
Day la bai toan tim cac so nguyen to tu 1 den n
*/
#include <stdio.h>
#include <math.h>
int ktnt(int n);
main()
{
int n,i;
printf("Please, enter an integer number ( n>=5 ): ");scanf("%d",&n);
if (n<2)return 0;
else if (n<4)
for(i=2;i<=n;i++)
printf("%4d",i);
else
{
printf(" 2 3");
for (i=5;i<=n;i+=2)
if ((i % 6 == 1 || i % 6 == 5) && ktnt(i))
printf("%4d",i);
}
}
int ktnt(int n) //Ham ktnt nay khong chuan muc voi nhieu bai
{
int i;
for (i=3;i<=sqrt(n);i++)
if (n%i==0) return 0;
return 1;
}
Số chắn không phải là số nguyên tố? Cái này chưa chích sác đâu. Người ta mới chỉ đưa ra giả định như vậy thôi. Ada 02-09-2009, 02:04 AM Có vài kết quả lí thú về công thức tính số nguyên tố. Không tồn tại phân thức đại số nào chỉ cho giá trị là số nguyên tố. Không tồn tại đa thức hệ số nguyên nào chỉ cho giá trị là số nguyên tố. Tuy vậy, tồn tại (nhiều) công thức dưới dạng đa thức hệ số nguyên và các biến số nguyên không âm mà phần miền giá trị dương trùng với tập hợp các số nguyên tố. Những công thức như thế đều khá phức tạp nên có lẽ chỉ có giá trị lí thuyết.
Trong công nghệ thông tin, có lẽ người ta quan tâm đến những công thức đơn giản, đảm bảo sinh ra số nguyên tố, nhưng không nhất thiết sinh ra tất cả các số nguyên tố. Về phương diện này, lí thú nhất có lẽ là định lí bảo rằng với mọi n tồn tại a, b sao cho với mọi x < n, số a x + b nguyên tố. Nhưng, đến nay công thức "tốt nhất" có dạng này mới chỉ dừng lại với n=25:
6171054912832631 + 81737658082080 x là số nguyên tố với x = 0, 1, 2, ..., 24.
Công thức này vẫn còn quá nhỏ cho nhu cầu thực tiễn của công nghệ thông tin (ví dụ, chữ ký số) => Hơi buồn một chút. clchicken 17-10-2011, 05:15 PM Mình thì nghĩ thế này :
với n>2 là số nguyên tố khi thỏa mãn cả 2 điều kiện sau :
1) n là số lẻ
2) n không chia hết cho tập hợp các số nguyên tố nhỏ hơn n/2
với thuật toán này :
Mình đã kiếm dc tập hợp số nguyên tố nhỏ hơn N :
N=1E6 , mất 15s
N=1E7 , mất 883s = 14,5 phút
như vậy ko biết là dc ko chưa? hay vẫn còn chậm ?
Theo mình thì thuật toán này vẫn là độ phức tạp O(n) .
Bạn có sàng n là số lẻ, n là số ko chia hết cho 3, ko chia hết cho 5, cho 7 ... thì độ phức tạp vẫn là tuyến tính với n . suy ra nó vẫn là O(n).
Phương pháp này gọi là phương pháp sàng gì gì đấy của 1 nhà toán học cổ đại . Quên mất cái tên :D
Nhưng nếu cho dù bạn ko sàng như vậy mà thu không gian xét về sqrt(n) thì độ phức tạp là O(sqrt(n)) . Nhanh hơn nhiều so với O(n).
-----------------
Theo ngu kiến của mình là phương pháp của chủ topic và các bạn đang bàn luận là 1 phép sàng nhỏ trong phép sàng tổng quát .
Và tóm lại có sàng nhiều đến đâu thì Không gian cần kiểm tra vẫn tuyến tính với sqrt(n) khị bạn cho vòng lặp chạy đến sqrt(n) . Do đó nó vẫn là O(sqrt(n)) :P ^^
Lợi được việc bỏ qua các số trong phép sàng thì lại bị thiệt ở chỗ phải kiểm tra xem số đó có nằm trong dãy số mình sàng ko. ^^
Bạn đưa vào danh sách các số sàng càng nhiều thì các số được bỏ qua cũng nhiều theo và số phép kiểm tra cũng tăng theo luôn :D daotien0887 25-09-2012, 11:08 AM Theo mình thì thuật toán này vẫn là độ phức tạp O(n) .
Bạn có sàng n là số lẻ, n là số ko chia hết cho 3, ko chia hết cho 5, cho 7 ... thì độ phức tạp vẫn là tuyến tính với n . suy ra nó vẫn là O(n).
Phương pháp này gọi là phương pháp sàng gì gì đấy của 1 nhà toán học cổ đại . Quên mất cái tên :D
Nhưng nếu cho dù bạn ko sàng như vậy mà thu không gian xét về sqrt(n) thì độ phức tạp là O(sqrt(n)) . Nhanh hơn nhiều so với O(n).
-----------------
Theo ngu kiến của mình là phương pháp của chủ topic và các bạn đang bàn luận là 1 phép sàng nhỏ trong phép sàng tổng quát .
Và tóm lại có sàng nhiều đến đâu thì Không gian cần kiểm tra vẫn tuyến tính với sqrt(n) khị bạn cho vòng lặp chạy đến sqrt(n) . Do đó nó vẫn là O(sqrt(n)) :P ^^
Lợi được việc bỏ qua các số trong phép sàng thì lại bị thiệt ở chỗ phải kiểm tra xem số đó có nằm trong dãy số mình sàng ko. ^^
Bạn đưa vào danh sách các số sàng càng nhiều thì các số được bỏ qua cũng nhiều theo và số phép kiểm tra cũng tăng theo luôn :D
Độ phức tạp thuật toán chỉ là tính mức max của 1 trường hợp thôi, sử dụng cận trên nên chưa chắc là o(n) > O(sqrt(n) trong trường hợp cụ thể.
Ở đây số số nguyên tố nhỏ hơn n/2 sẽ nhỏ hơn nhiều số từ 1 -> sqrt(n) với số lớn vì khi giá trị lên càng cao thì các số nguyên tố cũng thưa dần.
Nhưng với phương pháp của clamvn là phương pháp sàng số nguyên tố, nó tốt khi đã có sẵn sàng số nguyên tố hay là bài toán liệt kê số nguyên tố nhỏ hơn n, vì khi đó ta vừa liệt kê vừa tạo sàng snt.
Còn nếu bài toán kiểm tra 1 số lớn là snt hay ko thôi thì cách này lại kém hiệu quả khi chưa có sẵn sàng số nguyên tố. Jonhny_vinh 31-10-2012, 11:54 AM mình mới tìm ra thuật toán tìm số nguyên tố, với độ phức tạp khá đơn giản O(n);
ở đây mình muốn biết có bao nhiu số nguyên tố trong 1 khoảng số nào đó. Ví dụ từ 2 -> 1000 sẽ có bao nhiu số nguyên tố. và in những số đó ra màn hình. mình có 1 biến count để đếm.
mình viết bằng C# nhé;
puclic void SNT()
{
int snt =2; int count =0;// count sẽ đếm số lượng sô nguyên tố
int n = 1000 \\ n là số max của dãy số mà bạn muốn tìm số nguyên tố. ở đây tui tìm từ 2 -> 1000
while(snt < n)
{
if(snt == 2 || snt == 3 || snt == 5 || snt ==7)
{
console.WriteLine("{0} là số nguyên tố thứ {1}",snt,count);
count +=1;
}
else if(snt%2 != 0 && snt%3!=0 && snt%5!=0 && snt%7 ==0)
{
console.WriteLine("{0} là số nguyên tố thứ {1}",snt,count);
count +=1;
}
snt +=1;
// snt không thể chia cho 2 và 3 và 5 và 7 thì nó là số nguyên tố.
}
}
kết luận: thông thường khi bạn tìm số nguyên tố n , thì ít nhất bạn phải chia n cho đến n/2.
tức là nếu snt của bạn là 101 thì bạn phải chia nó ít nhất là 50 lần.
// còn giải thuật của mình. dù số nguyên tố của bạn có là 1 số với n chữ số cũng chỉ chia 4 lần. cho 2 3 5 và 7
ví dụ: snt của bạn là 101. giải thuật thông thường bạn phải chia 50 lần. còn của mình chia 4 lần như vậy giải thuật của mình nhanh hơn 50/4 = 12,5 lần. và nếu số nguyên tố đó càng lớn thì giải thuật của mình càng nhanh
Bạn nào ko tin test thử xem nhé(=D)> dangkhoasdc 31-10-2012, 03:49 PM mình mới tìm ra thuật toán tìm số nguyên tố, với độ phức tạp khá đơn giản O(n);
ở đây mình muốn biết có bao nhiu số nguyên tố trong 1 khoảng số nào đó. Ví dụ từ 2 -> 1000 sẽ có bao nhiu số nguyên tố. và in những số đó ra màn hình. mình có 1 biến count để đếm.
mình viết bằng C# nhé;
puclic void SNT()
{
int snt =2; int count =0;// count sẽ đếm số lượng sô nguyên tố
int n = 1000 \\ n là số max của dãy số mà bạn muốn tìm số nguyên tố. ở đây tui tìm từ 2 -> 1000
while(snt < n)
{
if(snt == 2 || snt == 3 || snt == 5 || snt ==7)
{
console.WriteLine("{0} là số nguyên tố thứ {1}",snt,count);
count +=1;
}
else if(snt%2 != 0 && snt%3!=0 && snt%5!=0 && snt%7 ==0)
{
console.WriteLine("{0} là số nguyên tố thứ {1}",snt,count);
count +=1;
}
snt +=1;
// snt không thể chia cho 2 và 3 và 5 và 7 thì nó là số nguyên tố.
}
}
kết luận: thông thường khi bạn tìm số nguyên tố n , thì ít nhất bạn phải chia n cho đến n/2.
tức là nếu snt của bạn là 101 thì bạn phải chia nó ít nhất là 50 lần.
// còn giải thuật của mình. dù số nguyên tố của bạn có là 1 số với n chữ số cũng chỉ chia 4 lần. cho 2 3 5 và 7
ví dụ: snt của bạn là 101. giải thuật thông thường bạn phải chia 50 lần. còn của mình chia 4 lần như vậy giải thuật của mình nhanh hơn 50/4 = 12,5 lần. và nếu số nguyên tố đó càng lớn thì giải thuật của mình càng nhanh
Bạn nào ko tin test thử xem nhé(=D)>
Thuật toán này chỉ đúng khi n<= 1000. Nếu lớn hơn 1000 thì sẽ bị sai :(.
Thuật toán của bạn khá giống dùng sàn :D vt240911 01-04-2013, 11:47 PM Bài toán này đã trở nên rất đỗi quen thuộc với chúng ta, trong bài này chúng ta sẽ bàn đến cách kiểm tra 1 số nguyên N cho trước có nguyên tố hay không trong phạm vi kiến thức số học sơ cấp.
Có rất nhiều cách, các cách thông thường là:
+ Xét các số từ 1 đến N xem có bao nhiêu số là ước của N rồi so sánh với 2. Cách này chạy rất chậm!
+ Xét các số từ 2 đến sqrt(N) rồi nếu là ước của N thì dừng lại, nhanh hơn 1 chút!
Ta sẽ bàn 1 cách nhanh hơn nữa:
Rõ ràng cái ta cần là làm sao giảm bớt số lượng số phải đem ra thử có phải là ước của N hay không. Trong danh sách này, có thể thừa (như 2 cách trên thừa rất nhiều) nhưng tuyệt đối không được thiếu các số nguyên tố bé hơn hoặc bằng sqrt(N). Vậy thì ta sẽ duyệt các số này theo 1 quy luật nào đó. Quy luật đó là gì?
Nhận xét: 1 số nguyên tố chia cho 6 dư 1 hoặc 5 (dễ dàng chứng minh) suy ra tập các số nguyên chia 6 dư 1 hoặc 5 sẽ bao trùm tập các số nguyên tố.
Từ đây ta có thuật toán: ta chỉ xét các số bé hơn hoặc bằng sqrt(N) mà chia 6 dư 1 hoặc 5 mà thôi, nếu N chia hết cho bất cứ 1 số nào trong đó thì N là hợp số, trái lại N là nguyên tố.
không phải ngẩu nhiên mà tôi chọn hằng số k= 6 này. Bài toán trở thành tìm số k mà từ 1 tới k-1 có ít số nguyên tố cùng nhau với nó nhất. Khi đó tỉ lệ phải xét chính là tỉ số các số nguyên tố cùng nhau này với k
thực nghiệm thì thấy số k tổng quát là tích của vài số nguyên tố đầu tiên, tất nhiên càng nhiều thì tỉ lệ phải xét càng nhỏ nhưng cài đặt có phần phức tạp hơn
các bạn mới làm toán thì bỏ qua tìm số k này, giỏi lên một tí các bạn cho k=2 để loại các số chẳn
rồi k=6 để loại các số chia hai huặc ba
nếu k=2*3*5=30( tỉ lệ phải xét, 4/15) thì tốc độ đc cải thiện đáng để, bạn thử cài đặt nhé, chú ý cái đặt thế nào cho thông minh
khi nghịch mã nguồn của Maple thì thấy nó lấy k là tích các số nguyên tố <1000 cơ
1 phát hiện hay đó, thank bạn nhìu |
