Một phương pháp lập bảng số nguyên tố
Ngô Minh Đức
Trong bài viết này tôi xin giới thiệu một phương pháp lập bảng số nguyên tốkhác, ngoài
phương pháp sàng Eratosthenes đã qúa quen thuộc với cácbạn.
Xin nhắc lại về sàng Eratosthenes (mang tên nhà toán học Hy Lạp, 275 - 194 TCN):
- Ta sắp xếp các số tự nhiên từ 2 đến N vào một bảng theo thứ tự 2,3,4,5,... N.
- Lưu lại số 2, lần lượt xóa đi các bội số của 2.
- Sau số 2, số không bị xóa đầu tiên là số 3, lần lượt xóa đi các bội số của 3
- Sau số 3, số không bị xóa đầu tiên là số 5, lần lượt xóa đi các bội số của 5,...
- Lặp lại đến khi không thể xóa được nữa thì thôi
Như vậy các số không bị xóa lập thành bảng các số nguyên tố nhỏ hơn hoặc bằng N.
Trong bộ sách ″Câu Chuyện Toán Học″ (một bộ sách rất hay gồm 6 tập của các thầy
Nguyễn Bá Đô, Đỗ Mạnh Hùng và Nguyễn Văn Túc), tập 3 có giới thiệu một phương pháp
lập bảng số nguyên tố khác. Tôi xin trình bày lạiở đây:
Học sinh Sundaram người ấn Độ đã đưa ra phương pháp này năm 1934.
Trước tiên Sundaram liệt kê một bảng các số như sau:
4 7 10 13 16 19 22...
7 12 17 22 27 32 37...
10 17 24 31 38 45 52... (1)
13 22 31 40 48 58 67...
16 27 38 49 60 71 82...
.....................
Bảng số này có tính đối xứng (số ở hàng m cột n bằng số hàng n cột m)
Các số này được chọn bằng cách lần lượt thực hiện các bước sau đây:
1. Viết số 4 vào góc bên trái
2. Các số tiếp theo của hàng 1 lần lượt là số liền trước cộng thêm 3 (các sốtrên hàng 1 lập
thành cấp số cộng với công sai là 3)
3. Các số tiếp theo của hàng 2 lần lượt là số liền trước cộng thêm 5 (các sốtrên hàng 5 lập
thành cấp số cộng với công sai là 5)
.......
Dễ dàng tìm được công thức để tính giá trị số thứ m hàng thứ n:

Đây là thủ tục thể hiện sàng Eratosthenes, vì đã qúa quen thuộc nên có lẽ không cần giải
thích nhiều với các bạn. Lưu ý một chút là ta chỉ cần xétcác số từ 2 đến sqrt(N):
Private Sub Eratosthenes()
'----------------------------------------------------------------------------------------------------------
' Thủ tục: Eratosthenes()
' Lập bảng số nguyên tố bằng sàng Eratosthenes
'----------------------------------------------------------------------------------------------------------
Dim I As Long
Dim K As Long
ReDim Mark(N) ′ định lại dung lượng cho mảng
Mark(0) = 1: Mark(1) = 1 ' 0 và 1 không phải số nguyên tố
' sử dụng sàng Eratosthenes
For I = 2 To Int(Sqr(N))
IfMark(I) = 0 Then ' nếu i là số nguyên tố
K= I * 2 ' gạch các bội số của i
Do While K >N/2 thì dừng lại
Xét hàng 2, tất nhiên xét từ ô (2,2) để bỏ qua giá trị trùng lặp, cho đến sốhạng > N/2 thì
dừng lại...
Cho đến hàng n mà giá trị của ô (n,n)>N/2 thì dừng lại.
ở mỗi số hạng K tìm thấy, ta đều đánh dấu Mark(K)=1 để chỉ 2*K+1 là hợp số
Toàn bộ qúa trình trên là để xác định trong phạm vi 2->N/2, số nào có trong bảng, số nào
không có trong bảng. Nhờ đó mà xác định được từ 2->N,số nào là số nguyên tố, số nào là
hợp số.
Thủ tục như sau:
Private Sub Sundaram()
'----------------------------------------------------------------------------------------------------------
' Thủ tục: Sundaram()
' Tạo bảng số nguyên tố bằng phương pháp của Sundaram
'----------------------------------------------------------------------------------------------------------
DimM As Long

DimI As Long
DimJ As Long
DimK As Long
DimP As Long
OpenFileName For Output As #1
' tiêu đề
Print#1, Space(20) & 'Bang cac so nguyen to tu 2 den ' & N
K = 6 ' viếtmột hàng 6 số
I = 0
Do
If Mark(I) =0 Then
IfKind Then ' sàng Eratosthenes
P= I ' Mark(I)=0 thì số nguyên tố cần viết là I
Else' sàng của Sundaram
P= IIf(I = 0, 2, 2 * I + 1) ' quy ước số nguyên tố cần viết = 2 nếuI=0,...
EndIf
IfK = 6 Then
Print#1, ' xuống dòng
K= 1
Else K = K + 1
EndIf
Print#1, Space(11 - Len(CStr(P))) + CStr(P); ' căn lề phải sao cho mỗi số đựơc12 kí tự
EndIf
I= I + 1
LoopUntil ((I > N/ 2) And (Not Kind)) Or (I > N) ' chỉ duyệt đến N/2 vớiphương pháp của
Sundaram
Close #1
End Sub
Ví dụ đểsử dụng thủ tục:
Sub Main()