Thông tin
  • Đánh dấu xác nhận câu hỏi đã được giải quyết để giúp diễn đàn nâng cao chất lượng [cách sử dụng]
  • Vui lòng đọc nội qui diễn đàn để tránh bị xóa bài viết [nội qui]
  • Tìm kiếm trước khi đặt câu hỏi

Một số vấn đề với số nguyên tố

Đây là nơi để các bạn trao đổi về cấu trúc dữ liệu và giải thuật

Điều hành viên: Điều hành

Một số vấn đề với số nguyên tố

Gửi bàigửi bởi tdat00 » Chủ nhật 16/05/2010 3:50 pm

Số nguyên tố (Prime Number) là một phần quan trọng không thể thiếu trong một số bài toán, nhất là lĩnh vực bảo mật (mã hóa RSA toàn xử lý số nguyên tố lớn, luôn lớn hơn 2000 bit). Vì thế việc cài đặt một thuật toán xử lý số nguyên tố không cần dễ hiểu, dễ cài đặt mà quan trọng nhất chính là tốc độ xử lý.

Có một số vấn đề với số nguyên tố em nêu ra để thảo luận với các bác, những vấn đề này xưa rồi, nhưng yêu cầu là tốc độ chạy phải nhanh trong khi thuật toán tương đối dễ cài đặt nhé:


1. Kiểm tra một số có phải là số nguyên tố.
2. Nhập vào một số bất kì, phân tích số đó ra các thừa số nguyên tố.
3. Nhập vào 2 số A < B. Đếm xem trong khoảng A - B có bao nhiêu số nguyên tố.
4. Nhập vào một số, tìm số nguyên tố nhỏ nhất và lớn hơn số này (get next prime)
5. (cao cấp) tìm một số nguyên tố mạnh khá lớn (lớn bao nhiêu tùy từng người).

Các vấn đề trên em xếp từ đơn giản đến phức tạp (theo cách nghĩ của em). Hix, em vẫn đang dừng ở vấn đề 1. Đang mày mò cài đặt các phép kiểm tra xác suất đây :(
Kẻ đẹp trai nhất chính là ta
Dung nham ngẫm kĩ cũng mặn mà
Hok biết ba trăm năm lẻ nữa
Thế gian ai có đẹp hơn ta

Há Há Há :)) :)) :))
Hình đại diện của thành viên
tdat00
Thành viên tích cực
Thành viên tích cực
 
Bài viết: 136
Ngày tham gia: Thứ 7 29/03/2008 8:18 am
Đến từ: QNgãi
Đã cảm ơn: 8 lần
Được cảm ơn: 2 lần

Re: Một số vấn đề với số nguyên tố

Gửi bàigửi bởi tdat00 » Chủ nhật 16/05/2010 3:53 pm

1. Kiểm tra một số có phải là số nguyên tố


Cách đơn giản nhất mà những ai mới nhập môn lập trình đều làm:

Syntax: [ Download ] [ Hide ]
Using C# Syntax Highlighting
  1. private bool IsPrime_VerySimple(ulong input)
  2. {
  3.     if (input < 2)
  4.         return false;
  5.  
  6.     ulong mid = input / 2;
  7.  
  8.     for (ulong i = 2; i <= mid; i++)
  9.     {
  10.         if (input % i == 0)
  11.             return false;
  12.     }
  13.  
  14.     return true;
  15. }
  16.  
Parsed in 0.000 seconds, using GeSHi 1.0.8.11



Và cách được dùng nhiều nhất hiện nay (có lẽ thế):

Syntax: [ Download ] [ Hide ]
Using C# Syntax Highlighting
  1. private bool IsPrime_MostCommon(ulong input)
  2. {
  3.     if (input < 2)
  4.         return false;
  5.  
  6.     if (input == 2)
  7.         return true;
  8.  
  9.     if (input % 2 == 0)
  10.         return false;
  11.  
  12.     ulong sqrt = (ulong)Math.Sqrt(input);
  13.  
  14.     for (ulong i = 3; i <= sqrt; i = i + 2)
  15.     {
  16.         if (input % i == 0)
  17.             return false;
  18.     }
  19.  
  20.     return true;
  21. }
  22.  
Parsed in 0.000 seconds, using GeSHi 1.0.8.11


Nhưng em mới phát hiện được 1 cách nữa (Source):
(Thuật toán này dựa vào nhận xét số nguyên tố luôn có dạng 6k + 1 hoặc 6k - 1)

Syntax: [ Download ] [ Hide ]
Using C# Syntax Highlighting
  1. private bool IsPrime_New(ulong input)
  2. {
  3.     if (input < 2)
  4.         return false;
  5.  
  6.     if (input == 2)
  7.         return true;
  8.  
  9.     if (input % 2 == 0)
  10.         return false;
  11.  
  12.     if (input == 3)
  13.         return true;
  14.  
  15.     if (input % 3 == 0)
  16.         return false;
  17.  
  18.     ulong i = 5;
  19.     ulong w = 2;
  20.     ulong sqrt = (ulong)Math.Sqrt(input);
  21.  
  22.     while (i <= sqrt)
  23.     {
  24.         if (input % i == 0)
  25.             return false;
  26.  
  27.         i = i + w;
  28.         w = 6 - w;
  29.     }
  30.  
  31.     return true;
  32. }
  33.  
Parsed in 0.000 seconds, using GeSHi 1.0.8.11


Dĩ nhiên ta có thể tăng lên nhận xét như số nguyên tố luôn có dạng 30k ± i với i = 1, 7, 11, 13 (30 = 2*3*5)... nhưng như thế sẽ đi theo hướng sàng số Eratosthenes mà việc cài đặt sẽ dài dòng hơn.

Bảng test thử các thuật toán:
Hình ảnh


Project: http://www.box.net/shared/lxpprcs35t

---------------------------------

PS: để kiểm tra số 1111111111111111111 (1 tỷ tỷ) không biết thuật toán 1 mất bao lâu, chỉ biết em đợi đến 30' nó vẫn chưa chạy xong, vào debug xem thử đã tới đâu thì i mới tới 42 tỷ thôi :( )
Kẻ đẹp trai nhất chính là ta
Dung nham ngẫm kĩ cũng mặn mà
Hok biết ba trăm năm lẻ nữa
Thế gian ai có đẹp hơn ta

Há Há Há :)) :)) :))
Hình đại diện của thành viên
tdat00
Thành viên tích cực
Thành viên tích cực
 
Bài viết: 136
Ngày tham gia: Thứ 7 29/03/2008 8:18 am
Đến từ: QNgãi
Đã cảm ơn: 8 lần
Được cảm ơn: 2 lần

Re: Một số vấn đề với số nguyên tố

Gửi bàigửi bởi longvannguyen.dx » Thứ 5 17/06/2010 8:27 pm

Như thế này nhá:
Xét số n > 6 (Trường hợp < 6 thì kiểm tra n = 1, 4, 6 thì không phải là số nguyên tố, n = 3,5 thì là số nguyên tố)
Bước 1:
Một số bất kì n (n>6) đem chia cho 6:
+Nếu được số dư là 1 hoặc 5 thì qua bước 2
+Ngược lại -->không phải là số nguyên tố !kết thúc
Bước 2:
+Đặt t bằng căn bậc 2 của n, tiếp tục lại đặt t = t*t,kiểm tra nếu t = n thì kết luận n không phải là số nguyên tố (bởi vì n là số chính phương), kết thúc
+Ngược lại -->n là số nguyên tố,kết thúc

Mô tả bằng hàm trong Pascal như sau:
Function KIEMTRA_SNT(n : Integer) : Boolean;
Var du : Byte; {số dư của n chia cho 6}
t : Real;
Begin
If (n <= 6) Then
If ((n = 1) Or (n = 4) Or (n = 6)) Then KIEMTRA_SNT := False Else KIEMTRA_SNT := True
Else
du = n mod 6;
If ((du = 1) Or (du = 5)) Then
Begin
{Kiểm tra n có phải là số chính phương hay không?}
t = sqrt(n);
t= t*t;
If (t = n) Then KIEMTRA_SNT := False Else KIEMTRA_SNT := True
End
Else KIEMTRA_SNT := False ;
End;

Trường hợp xấu nhất là n là số chính phương! ^.^
longvannguyen.dx
Thành viên chính thức
Thành viên chính thức
 
Bài viết: 15
Ngày tham gia: Chủ nhật 10/05/2009 9:05 pm
Đã cảm ơn: 0 lần
Được cảm ơn: 0 lần

Re: Một số vấn đề với số nguyên tố

Gửi bàigửi bởi vo_minhdat2007 » Thứ 5 17/06/2010 10:34 pm

Hay thật nhỉ :D Cách này kiểm tra ngay lập tức được số nguyên tố với thời gian không đáng kể, chỉ phụ thuộc vào chúng ta xử lí số lớn để đạt kết quả cần thiết thôi.

Nhưng theo như những cách trên thì để thực hiện yêu cầu từ 3 trở lên thì phải dùng For (tất nhiên có bước nhảy) để xác định vì thuật toán của chúng ta chỉ xác định số nguyên tố chứ không xác định được số tiếp theo :-? .
P/s: Hình như nếu làm được câu 4 thì sẽ làm được câu 3 dễ hơn?
Hình đại diện của thành viên
vo_minhdat2007
Quản trị
Quản trị
 
Bài viết: 2227
Ngày tham gia: Chủ nhật 17/07/2005 1:40 am
Đã cảm ơn: 13 lần
Được cảm ơn: 84 lần

Re: Một số vấn đề với số nguyên tố

Gửi bàigửi bởi longvannguyen.dx » Thứ 6 18/06/2010 8:09 pm

Thì muốn đưa ra tất cả số nguyên tố trong đoạn [A,B] thì phải dùng For thui chứ sao nữa!, nhưng để cải tiến ta thì ta chỉ kiểm tra những số chia hết cho 6 được số dư là 1 hoặc 5 và những số không phải là số chính phương!
Còn bạn nào có cách giải quyết tốt hơn thì post cho các bạn học hỏi!
longvannguyen.dx
Thành viên chính thức
Thành viên chính thức
 
Bài viết: 15
Ngày tham gia: Chủ nhật 10/05/2009 9:05 pm
Đã cảm ơn: 0 lần
Được cảm ơn: 0 lần

Re: Một số vấn đề với số nguyên tố

Gửi bàigửi bởi T7 » Thứ 4 23/06/2010 5:01 pm

Nói 1 chút về thuật toán Sieve of Eratosthenes

Trong toán học, Sieve of Eratosthenes là 1 thuật toán cổ điển dùng để tìm kiếm tất cả các số nguyên tố từ 1 đến 1 số bất kì N, mà thích hợp nhất là tìm các số nguyên tố nhỏ hơn N = 1 tỷ (không biết máy khác ntn chứ máy em cho nó liệt kê hơn 1 tỷ là nó bắt đầu bị "Freeze" cũng hơi lâu rồi :P ).
Cách hoạt động của thuật toán cũng rất đơn giản qua 6 bước sau:
1. Tạo mảng chứa các số {2,3,4,...,N-1,N}.
2. Xét từ trái qua phải, số đầu tiên của mảng là a=2 (số nguyên tố đầu tiên).
3. Tìm tất cả những số trong dãy là bội của a=2, tức là {2,4,6,8,...} và loại bỏ những số đó ra khỏi mảng.
4. Tìm số tiếp theo trong mảng sau số a, gáng số đó cho a.
5. Lập lại bước 3 và 4 cho tới khi a^2 lớn hơn N.
6. In tất cả những số còn lại trong mảng ra, và đó là những số nguyên tố từ 1 đến số N.
Hình ảnh

Về độ phức tạp thì thuật toán có độ phức tạp là: O(n(log(n))(log(log(n))).
Người ta đã chứng minh được rằng thuật toán thuộc hàng "cổ" này còn liệt kê các số nguyên tố nhanh hơn cả các thuật toán mới nhất bây giờ (chẳng hạn thuật toán Turner)

Ta cũng có thể dùng thuật toán Sieve of Eratosthenes để kiểm tra 1 số N nào đó có phải là số nguyên tố hay không bằng cách liệt kê tất các số nguyên tố mà bình phương nhỏ hơn hoặc bằng N. Sau đó kiểm tra xem N có chia hết cho số nào trong các số nguyên tố đó không. Nếu không thì N là số nguyên tố.
VD: Để kiểm tra số 1000000000 (1 tỷ) có phải là số nguyên tố hay ko, ta liệt kê tất cả các số nguyên tố mà bình phương nhỏ hơn hoặc bằng N, tức là liệt kê các số nguyên tố nhỏ hơn hoặc bằng 31622. Có khoảng 3500 số nguyên tố trong khoảng này, như vậy nếu ko kể thời gian liệt kê các số nguyên tố thì thời gian để kiểm tra số 1 tỷ có phải 1 số nguyên tố hay ko là 1 thuật toán với độ phức tạp O(n) và chỉ dùng khoảng 3500 lần lặp, so với thuật toán O(n) tìm số nguyên tố tốt nhất đã trình bày ở trên thì trong trường hợp TB là phải dùng SQRT(1000000000)/6 ~5270 lần lặp.

Đây chính là phương pháp dùng sàng Eratosthenes mà tdat00 đã trình bày :D
Sửa lần cuối bởi T7 vào ngày Chủ nhật 27/06/2010 8:05 pm với 2 lần sửa trong tổng số.
While (i <= you) i++;
Hình đại diện của thành viên
T7
Thành viên danh dự
Thành viên danh dự
 
Bài viết: 415
Ngày tham gia: Thứ 5 24/05/2007 8:19 pm
Đến từ: Long Xuyên - An Giang
Đã cảm ơn: 0 lần
Được cảm ơn: 12 lần

Re: Một số vấn đề với số nguyên tố

Gửi bàigửi bởi Uzumaki Naruto » Thứ 4 23/06/2010 5:25 pm

Hơ hơ. Giờ T7 tóm tắt mới rõ, chứ trước đó cứ tù mù tờ mờ, làm thì biết code nhưng cũng hiểu chẳng dc nhiêu, thanks T7
Cause you're my special thing
I'm flying without wings
Uzumaki Naruto
Thành viên ưu tú
Thành viên ưu tú
 
Bài viết: 827
Ngày tham gia: Thứ 2 30/04/2007 9:55 pm
Đến từ: Sài Gòn
Đã cảm ơn: 7 lần
Được cảm ơn: 79 lần

Re: Một số vấn đề với số nguyên tố

Gửi bàigửi bởi vo_minhdat2007 » Thứ 4 23/06/2010 6:57 pm

Thanks T7. À cái hình đó em lấy từ trên mạng hay tự làm vậy? Nếu làm thì dùng phần mềm nào cho tiện? Chứ chẳng lẽ ngồi gạch từng cái à :P
Hình đại diện của thành viên
vo_minhdat2007
Quản trị
Quản trị
 
Bài viết: 2227
Ngày tham gia: Chủ nhật 17/07/2005 1:40 am
Đã cảm ơn: 13 lần
Được cảm ơn: 84 lần

Re: Một số vấn đề với số nguyên tố

Gửi bàigửi bởi T7 » Thứ 4 23/06/2010 7:40 pm

@Uzumaki Naruto: Hì, ko có chi. Em thấy hay hay nên giới thiệu cho mọi người biết thôi :D

vo_minhdat2007 đã viết:Thanks T7. À cái hình đó em lấy từ trên mạng hay tự làm vậy? Nếu làm thì dùng phần mềm nào cho tiện? Chứ chẳng lẽ ngồi gạch từng cái à :P

À, cái hình đó em lấy trên trang wikipedia.org ấy, mà em nghĩ chắc là họ dùng Macromedia Flash viết code cho nó tự động gạch lên tấm hình theo thuật toán rồi xuất ra dạng ảnh gif thôi :D
While (i <= you) i++;
Hình đại diện của thành viên
T7
Thành viên danh dự
Thành viên danh dự
 
Bài viết: 415
Ngày tham gia: Thứ 5 24/05/2007 8:19 pm
Đến từ: Long Xuyên - An Giang
Đã cảm ơn: 0 lần
Được cảm ơn: 12 lần

Re: Một số vấn đề với số nguyên tố

Gửi bàigửi bởi tdat00 » Thứ 7 26/06/2010 9:27 am

Các cách trên vẫn không có tính ứng dụng thực tế. Hiện tại người ta dùng phép kiểm tra Miller - Rabin kìa. Em thử vào mấy website check số nguyên tố trực tuyến, họ dùng MR kiểm tra chưa đầy 2 giây dù cho mình có nhập bao nhiêu chữ số đi nữa.

Em cài đặt thuật toán MR trong C# mãi mà sao vẫn báo ko đúng, chẳng hiểu sai chỗ nào nữa, tham khảo biết bao nhiêu source rồi :(

Giờ .Net 4 hỗ trợ BigInteger rồi cũng đỡ, chứ hồi xưa phải dùng string để xử lý thì :((
Kẻ đẹp trai nhất chính là ta
Dung nham ngẫm kĩ cũng mặn mà
Hok biết ba trăm năm lẻ nữa
Thế gian ai có đẹp hơn ta

Há Há Há :)) :)) :))
Hình đại diện của thành viên
tdat00
Thành viên tích cực
Thành viên tích cực
 
Bài viết: 136
Ngày tham gia: Thứ 7 29/03/2008 8:18 am
Đến từ: QNgãi
Đã cảm ơn: 8 lần
Được cảm ơn: 2 lần

Re: Một số vấn đề với số nguyên tố

Gửi bàigửi bởi vuathongtin » Chủ nhật 27/06/2010 12:25 pm

Mình xin nói thêm về Sieve of Eratosthenes 1 tí

Ban đầu, nhà toán học Eratosthenes sau khi tìm ra thuật toán, đã lấy lá cọ và ghi tất cả các số từ 2 cho đến 100. Ông đã chọc thủng các hợp số và giữ nguyên các số nguyên tố. Bảng số nguyên tố còn lại trông rất giống một cái sàng. Do đó, nó có tên là sàng Eratosthenes.


Chú ý: Sàng Eratosthenes chỉ ghi các số từ 2 đến 100 mà không ghi hai chữ số 0 và 1 cả hợp số lẫn số nguyên tố đều lớn hơn 0 và 1.

Theo thuật ngữ toán, ta có thể tìm các số nguyên tố bằng sàng Eratosthenes như sau:
* B1:Ta tìm các số chia hết cho 2, ngoại trừ chính nó.
* B2:Tìm các số chia hết cho 3, cũng không tính 3.
* B3:Tìm các số chia hết cho 5, trừ 5.
* B4:Ta tìm các số chia hết cho 7, trừ 7.
* B5:Chọn ra các số còn lại, chúng chính là số nguyên tố.

Hình minh họa cho thấy thuật toán đơn giản để tìm số nguyên tố và các bội số
Hình ảnh
Các số tô màu giống nhau là cùng một họ mà dẫn đầu (đậm hơn) sẽ là số nguyên tố


---> có vẻ như cách này dễ hiểu hơn
Nguồn :http://vi.wikipedia.org/wiki/S%C3%A0ng_Eratosthenes
Bạn nào rảnh thì viết chương trình Test thử xem
Bùi Thành Nhân
Chuyên viên CNTT - Sở Thông tin & Truyền thông tỉnh Phú Yên
giasulaptrinh.com
Hình đại diện của thành viên
vuathongtin
Điều hành viên
Điều hành viên
 
Bài viết: 1024
Ngày tham gia: Chủ nhật 02/05/2010 10:03 pm
Đến từ: Sở thông tin và truyền thông tỉnh Phú Yên
Đã cảm ơn: 2 lần
Được cảm ơn: 99 lần

Re: Một số vấn đề với số nguyên tố

Gửi bàigửi bởi vo_minhdat2007 » Chủ nhật 27/06/2010 2:32 pm

Có khác gì của T7 đâu? Thuật toán này thì đơn giản rồi, nhưng là tìm số nguyên tố từ 1 đến N.
Hình đại diện của thành viên
vo_minhdat2007
Quản trị
Quản trị
 
Bài viết: 2227
Ngày tham gia: Chủ nhật 17/07/2005 1:40 am
Đã cảm ơn: 13 lần
Được cảm ơn: 84 lần

Re: Một số vấn đề với số nguyên tố

Gửi bàigửi bởi vuathongtin » Chủ nhật 27/06/2010 5:48 pm

Hình ảnh


Sieve of Eratosthenes
Syntax: [ Download ] [ Hide ]
Using vb.net Syntax Highlighting
  1. Sub FindPrimes(ByVal n As Integer)
  2.         ListBox1.Items.Clear()
  3.  
  4.         Dim bandau As Long = Now.Ticks
  5.         Dim eliminated As New BitArray(n + 1)
  6.  
  7.         ListBox1.Items.AddRange(New Object() {"1", "2"})
  8.  
  9.         For i = 3 To n Step 2
  10.             If (Not eliminated(i)) Then
  11.                 If (i < Math.Sqrt(n)) Then
  12.                     For j = i * i To n Step 2 * i
  13.                         eliminated(j) = True
  14.                     Next
  15.                 End If
  16.                 ListBox1.Items.Add(i)
  17.             End If
  18.         Next
  19.     End Sub
  20.  
Parsed in 0.016 seconds, using GeSHi 1.0.8.11


Thuật toán 2 : (Theo cách thuật toán mình post ở trên)

Syntax: [ Download ] [ Hide ]
Using vb.net Syntax Highlighting
  1.  Sub sangsonguyento(ByVal n As Double)
  2.         ListBox1.Items.Clear()
  3.         Dim i As Double
  4.         For i = 0 To n + 1
  5.             A(i + 1) = i
  6.         Next
  7.  
  8.         For i = 1 To n + 1
  9.             If A(i) > 2 Then
  10.                 If A(i) Mod 2 = 0 Then
  11.                     A(i) = 0
  12.                 End If
  13.             End If
  14.  
  15.             If A(i) > 3 Then
  16.                 If A(i) Mod 3 = 0 Then
  17.                     A(i) = 0
  18.                 End If
  19.             End If
  20.  
  21.             If A(i) > 5 Then
  22.                 If A(i) Mod 5 = 0 Then
  23.                     A(i) = 0
  24.                 End If
  25.             End If
  26.  
  27.             If A(i) > 7 Then
  28.                 If A(i) Mod 7 = 0 Then
  29.                     A(i) = 0
  30.                 End If
  31.             End If
  32.  
  33.  
  34.         Next
  35.  
  36.         For i = 1 To n + 1
  37.             If A(i) <> 0 Then
  38.                 ListBox1.Items.Add(A(i))
  39.             End If
  40.         Next
  41.     End Sub
  42.  
  43.  
Parsed in 0.000 seconds, using GeSHi 1.0.8.11
Bạn không được cấp phép để xem tập tin đính kèm trong bài viết này.
Bùi Thành Nhân
Chuyên viên CNTT - Sở Thông tin & Truyền thông tỉnh Phú Yên
giasulaptrinh.com
Hình đại diện của thành viên
vuathongtin
Điều hành viên
Điều hành viên
 
Bài viết: 1024
Ngày tham gia: Chủ nhật 02/05/2010 10:03 pm
Đến từ: Sở thông tin và truyền thông tỉnh Phú Yên
Đã cảm ơn: 2 lần
Được cảm ơn: 99 lần

Re: Một số vấn đề với số nguyên tố

Gửi bàigửi bởi tdat00 » Chủ nhật 27/06/2010 8:17 pm

các bác thử cài đặt thuật toán Miller-Rabin đi. Cái sàn này thì... :(
Kẻ đẹp trai nhất chính là ta
Dung nham ngẫm kĩ cũng mặn mà
Hok biết ba trăm năm lẻ nữa
Thế gian ai có đẹp hơn ta

Há Há Há :)) :)) :))
Hình đại diện của thành viên
tdat00
Thành viên tích cực
Thành viên tích cực
 
Bài viết: 136
Ngày tham gia: Thứ 7 29/03/2008 8:18 am
Đến từ: QNgãi
Đã cảm ơn: 8 lần
Được cảm ơn: 2 lần

Re: Một số vấn đề với số nguyên tố

Gửi bàigửi bởi vo_minhdat2007 » Chủ nhật 27/06/2010 9:56 pm

Cái thuật toán đó em đọc chẳng hiểu được 8-}
Hình đại diện của thành viên
vo_minhdat2007
Quản trị
Quản trị
 
Bài viết: 2227
Ngày tham gia: Chủ nhật 17/07/2005 1:40 am
Đã cảm ơn: 13 lần
Được cảm ơn: 84 lần

Re: Một số vấn đề với số nguyên tố

Gửi bàigửi bởi Uzumaki Naruto » Chủ nhật 27/06/2010 10:28 pm

Chính xác, nói thiệt là điên cái đầu, đọc mãi vẫn chưa hiểu
Cause you're my special thing
I'm flying without wings
Uzumaki Naruto
Thành viên ưu tú
Thành viên ưu tú
 
Bài viết: 827
Ngày tham gia: Thứ 2 30/04/2007 9:55 pm
Đến từ: Sài Gòn
Đã cảm ơn: 7 lần
Được cảm ơn: 79 lần

Re: Một số vấn đề với số nguyên tố

Gửi bàigửi bởi tdat00 » Thứ 2 28/06/2010 9:31 am

Khà khà, tối qua mày mò lại thì em đã code được thuật toán Miller - Rabin bằng C# rồi :D

Về ý tưởng thuật toán thì wikipedia giải thích đúng: http://en.wikipedia.org/wiki/Miller-Rab ... ality_test tuy nhiên nếu code theo pseudocode của wikipedia sẽ chạy sai. Em search được cái ebook này và làm ok rồi (pseudocode của ebook này khác wikipedia chỗ nào thì các bác tự tìm hiểu nhé): http://www.cryptomathic.com/Files/Filer ... y_Test.pdf

Và đây là code bằng C# (dùng .Net 4.0 vì các phiên bản .Net trước chưa hỗ trợ kiểu BigInteger). Chú ý là các bác phải add reference thư viện System.Numerics mới dùng được kiểu BigInteger nhé:
Syntax: [ Download ] [ Hide ]
Using C# Syntax Highlighting
  1. /// <summary>
  2. /// Lấy một số ngẫu nhiên trong khoảng [min, max]
  3. /// </summary>
  4. /// <param name="min">Giới hạn nhỏ nhất</param>
  5. /// <param name="max">Giới hạn lớn nhất</param>
  6. public static BigInteger GetRandomBigInteger(BigInteger min, BigInteger max)
  7. {
  8.     Random r = new Random();
  9.     BigInteger res;
  10.     do
  11.     {
  12.         res = min + BigInteger.Multiply((max - min) / 1000, r.Next(1000));
  13.     }
  14.     while (res > max); // ko có chuyện res < min
  15.  
  16.     return res;
  17. }
  18.  
  19. /// <summary>
  20. /// Dùng thuật toán Miller-Rabin để kiểm tra một số có phải là số nguyên tố
  21. /// </summary>
  22. /// <param name="n">Số cần kiểm tra</param>
  23. public static bool IsPrimeNumber(BigInteger n)
  24. {
  25.     // Xác định số lần test. Xác suất để phép kiểm tra này bị sai là 4^(-SO_LAN_TEST).
  26.     // Với SO_LAN_TEST = 50, xác suất bị sai là 9*10^-29
  27.     int SO_LAN_TEST = 50;
  28.  
  29.     // Kiểm tra các số nhỏ hơn 5
  30.     if (n < 5)
  31.     {
  32.         if (n == 2 || n == 3)
  33.             return true;
  34.  
  35.         return false;
  36.     }
  37.  
  38.     if (n.IsEven) // Nếu là số chẵn
  39.         return false;
  40.  
  41.     BigInteger d, x;
  42.     int s = 1, r;
  43.  
  44.     // Phân tích n - 1 thành dạng 2^s*d với d lẻ
  45.     while (BigInteger.Remainder(n - 1, BigInteger.Pow(2, s + 1)) == 0)
  46.         s++;
  47.     d = BigInteger.Divide(n - 1, BigInteger.Pow(2, s));
  48.  
  49.     // kiểm tra đủ số lần test
  50.     for (int i = 1; i <= SO_LAN_TEST; i++)
  51.     {
  52.         // Lấy một số ngẫu nhiên a
  53.         BigInteger a = GetRandomBigInteger(2, n - 2);
  54.  
  55.         // Tính x = a^d mod n
  56.         x = BigInteger.ModPow(a, d, n);
  57.  
  58.         if (x.IsOne || x == n - 1) // nếu x == 1 hoặc x == n - 1 sẽ chuyển đến lần test kế (i + 1)
  59.             continue;
  60.  
  61.         for (r = 1; r < s && x != n - 1; r++)
  62.         {
  63.             x = BigInteger.ModPow(x, 2, n); // x = x^2 mod n
  64.             if (x.IsOne) // nếu x == 1 --> không phải số nguyên tố
  65.                 return false;
  66.         }
  67.         if (x != n - 1)
  68.             return false;
  69.     }
  70.  
  71.     // Nếu đã vượt qua đủ số lần test ---> là số nguyên tố
  72.     return true;
  73. }
Parsed in 0.016 seconds, using GeSHi 1.0.8.11


Hình ảnh

Như đã nói, thuật toán này cho phép kiểm tra các số cực lớn cỡ 1024 bit (128 chữ số) trở lên một cách nhanh chóng (code của em check chưa đầy một giây) với xác suất sai sót vô cùng nhỏ (khoảng 9*10^-29 nếu thực hiện 50 lần test). Kiểu này thì nghiên cứu RSA dễ dàng rồi :D

Ai muốn đối chứng thì vào trang này cho phép kiểm tra hoặc tạo số nguyên tố tối đa 1024-bit: http://www.numberempire.com/primenumbers.php
Bạn không được cấp phép để xem tập tin đính kèm trong bài viết này.
Kẻ đẹp trai nhất chính là ta
Dung nham ngẫm kĩ cũng mặn mà
Hok biết ba trăm năm lẻ nữa
Thế gian ai có đẹp hơn ta

Há Há Há :)) :)) :))
Hình đại diện của thành viên
tdat00
Thành viên tích cực
Thành viên tích cực
 
Bài viết: 136
Ngày tham gia: Thứ 7 29/03/2008 8:18 am
Đến từ: QNgãi
Đã cảm ơn: 8 lần
Được cảm ơn: 2 lần

Re: Một số vấn đề với số nguyên tố

Gửi bàigửi bởi tdat00 » Thứ 2 28/06/2010 9:35 am

À, giờ đến vấn đề 4: nhập 1 số nguyên n, tìm số nguyên tố nhỏ nhất và lớn hơn n. Em vẫn mới chỉ kiểm tra lần lượt các số lẻ lớn hơn n, nếu đúng thì in ra, ko thì tăng lên 2 đơn vị thôi. Thời gian cũng tạm chấp nhận được nhưng không biết có cách nào tối ưu hơn không :(
Kẻ đẹp trai nhất chính là ta
Dung nham ngẫm kĩ cũng mặn mà
Hok biết ba trăm năm lẻ nữa
Thế gian ai có đẹp hơn ta

Há Há Há :)) :)) :))
Hình đại diện của thành viên
tdat00
Thành viên tích cực
Thành viên tích cực
 
Bài viết: 136
Ngày tham gia: Thứ 7 29/03/2008 8:18 am
Đến từ: QNgãi
Đã cảm ơn: 8 lần
Được cảm ơn: 2 lần

Re: Một số vấn đề với số nguyên tố

Gửi bàigửi bởi vo_minhdat2007 » Thứ 2 28/06/2010 10:38 am

Hình như không còn cách nào khác. Các trang web cũng vậy thôi, check Prime thì rất nhanh, nhưng tìm Next Prime thì lại treo trình duyệt.
Hình đại diện của thành viên
vo_minhdat2007
Quản trị
Quản trị
 
Bài viết: 2227
Ngày tham gia: Chủ nhật 17/07/2005 1:40 am
Đã cảm ơn: 13 lần
Được cảm ơn: 84 lần

Re: Một số vấn đề với số nguyên tố

Gửi bàigửi bởi vuathongtin » Thứ 2 28/06/2010 10:55 am

Liệt Kê số nguyên tố bằng phép thử Miller Rabin
Syntax: [ Download ] [ Hide ]
Using vb.net Syntax Highlighting
  1.  Function nguyento(ByVal n As Double) As Boolean
  2.         Dim m As Double, b As Double, s As Double, i As Double
  3.         nguyento = True
  4.         m = n - 1
  5.         s = 0
  6.         b = 1
  7.  
  8.         While (m Mod 2) = 0
  9.             s += 1
  10.             m = m \ 2
  11.         End While
  12.  
  13.  
  14.         For i = 1 To m
  15.             b = (b * 2) Mod n
  16.         Next
  17.  
  18.         If b = 1 Then
  19.             Exit Function
  20.         ElseIf b <> 1 Then
  21.             For i = 0 To s - 1
  22.                 If (b Mod n) = n - 1 Then
  23.                     Exit Function
  24.                 Else
  25.                     b = (b * b) Mod n
  26.                 End If
  27.             Next
  28.         End If
  29.         nguyento = False
  30.     End Function
  31.  
Parsed in 0.016 seconds, using GeSHi 1.0.8.11


Cái này mình định post hôm qua nhưng bị một số lỗi nên hôm nay mới post được. Độ chính xác hình như có sự chênh lệch so với các thuật toán khác hay sao ý.
Nếu có gì sai sót thì góp ý nhen. :D

Nhân tiện cho các bạn xem sơ lược về bảng số nguyên tố, nhiều thứ thú vị lắm :P http://vi.wikipedia.org/wiki/B%E1%BA%A3ng_s%E1%BB%91_nguy%C3%AAn_t%E1%BB%91
Bạn không được cấp phép để xem tập tin đính kèm trong bài viết này.
Bùi Thành Nhân
Chuyên viên CNTT - Sở Thông tin & Truyền thông tỉnh Phú Yên
giasulaptrinh.com
Hình đại diện của thành viên
vuathongtin
Điều hành viên
Điều hành viên
 
Bài viết: 1024
Ngày tham gia: Chủ nhật 02/05/2010 10:03 pm
Đến từ: Sở thông tin và truyền thông tỉnh Phú Yên
Đã cảm ơn: 2 lần
Được cảm ơn: 99 lần

Trang kế tiếp

Quay về Cấu trúc dữ liệu và giải thuật

Ai đang trực tuyến?

Đang xem chuyên mục này: Không có thành viên nào đang trực tuyến1 khách