SKKN Nghiên cứu các cải tiến sàng Eratosthenes và áp dụng giải một số bài toán trong chương trình bồi dưỡng học sinh giỏi Tin học tại trường THPT Thanh Chương 1

Cho bạn một số nguyên dương T là số test cần xử lý. T dòng tiếp theo là T số 
nguyên dương M, hãy phân tích M ra thành tích các thừa số nguyên tố. 
Giới hạn là T <= 10
5 
và M <= 10
7
Em hãy giúp Minh vượt qua thử thách này nhé 
Input: từ tệp FACTOR.INP 
● Dòng đầu tiên chứa số lượng các test T 
● T dòng tiếp theo, mỗi dòng chứa số nguyên dương M 
Output: ghi ra tệp FACTOR.OUT 
● Xuất ra T chuổi là tích các thừa số nguyên tố nằm trên T dòng trả lời cho T 
test ở trên. 
Ràng buộc: giới hạn 1s 
Ví dụ: 
FACTOR.INP FACTOR.OUT 
2 
15 
30 
3*5 
2*3*5 
7 
Thuật toán: 
Ta có thể phân tích số M ra thừa số nguyên tố bằng thuật toán thông thường có độ 
phức tạp O(M) như sau: 
void factor(long M){ 
for(long i = 2; i*i <= M; ++i){ 
while (M % i == 0){ 
if (m/i !=1) fprintf(fo, "%ld*",i ); 
else fprintf(fo, "%ld",i ); 
M /= i; 
} 
} 
} 
Ví dụ: 
n = 30, i = 2, ans ={2} 
n = 15, i = 2, ans = {2} 
n = 15, i = 3, ans = {2, 3} 
n = 5, i = 4, ans = {2, 3} 
n = 5, i = 5, ans = {2, 3, 5} 
n = 1 
Tuy nhiên, với thuật toán trên ta chỉ giải quyết được bài toán với M tối đa là 104 do 
T là rất lớn. 
Cải tiến: 
Ta sẽ sử dụng sàng Eratosthenes để phân tích số M ra thừa số nguyên tố với 
độ phức tạp là O(logn) 
Nhận xét: Tại mỗi bước phân tích ta sẽ tìm số nguyên tố nhỏ nhất mà M chia 
hết. 
Từ nhận xét trên, ta sẽ dùng Sàng Eratosthenes để xác định số nguyên tố nhỏ 
nhất thỏa nhận xét trên trong thời gian O(1) 
int min_prime(){ 
for (long i = 2; i*i <= n; ++i) { 
 if (minprime [i] == 0) { 
 minprime [i] =i; 
 for (long j = i * i; j <= n; j += i) 
8 
 if (minprime[j] == 0) 
 minprime [j ] = i ; 
 } 
} 
return 0; 
} 
//------------------------- 
void factor (long m){ 
while (m !=1) { 
if (m/minprime[m] !=1) 
fprintf(fo, "%ld*",minprime[m] ); 
else fprintf(fo, "%ld\n", minprime[m] 
); m /= minprime[m]; 
} 
} 
Code full: 
#include 
using namespace std; 
#define n 10000000 
#define fi "factor.inp" 
#define fo "factor.out" 
long * minprime = new long [n+1]; 
FILE* ffi = freopen(fi, "r", stdin); 
FILE* ffo = freopen(fo, "w", stdout); 
//------------------------------- 
int min_prime(){ 
for (long long i = 2; i*i <= n; ++i) { 
 if (minprime [i] == 0) { 
 minprime [i] =i; 
 for (long long j = i * i; j <= n; j += i) if 
(minprime[j] == 0) 
 minprime [j ] = i ; 
9 
 } 
} 
for(long long i = 2; i<= n; ++i) 
 if (!minprime[i]) minprime[i] = i; 
return 0; 
} 
//------------------------------ 
void factor (long m){ 
while (m !=1) { 
if (m/minprime[m] !=1) 
fprintf(ffo,"%ld*",minprime[m] ); 
else fprintf(ffo,"%ld\n", minprime[m] 
); m /= minprime[m]; 
} 
} 
//----------------------------- 
void process(){ 
long t,m; 
fscanf(ffi,"%ld", &t); 
min_prime(); 
for (int i = 1; i<= t ; ++i){ 
fscanf(ffi,"%ld", &m); 
factor(m); 
} 
} 
//------------------------------ 
int main(){ 
process(); 
return 0; 
} 
Độ phức tạp: O(nlog(n)) 
10 
Bài 2. Tổng các số nguyên tố đầu tiên 
Cho một số nguyên dương N. Yêu cầu tính tổng của N số nguyên tố đầu 
tiên. Dữ liệu vào: cho trong tệp có cấu trúc: 
- Dòng đầu tiên chứa số T là số lượng bộ tests (1 ≤ T ≤ 103) 
- T dòng tiếp theo, mỗi dòng cha một số N (1 ≤ N ≤ 106). 
Kết quả ra: ghi ra tệp gồm T dòng, mỗi dòng ghi một số tương ứng là tổng của N 
số nguyên tố đầu tiên. 
Ví dụ: 
Dữ liệu vào Kết quả ra 
3 
5 
2 
7 
28 
5 
58 
Hướng dẫn: Tương tự bài 2, giá trị của số nguyên tố thứ N có thể lên đến 
10
8
. Vì vậy dùng sàng cải tiến kết hợp mảng tính trước tổng của N số nguyên tố 
đầu tiên. 
Code minh họa: 
#include 
using namespace std; 
#define MAX 100000000 
#define check(n) (prime[n>>6]&(1>1))) 
#define set(n) prime[n>>6]|=(1>1)) 
int t,n; 
long long sum[1000001]; 
int prime[MAX>>6]; 
void Era3(){ 
for(int i=3;i*i<=MAX;i+=2){ 
if (!check(i)){ 
int tmp = 2*i; 
for(int j=i*i;j<=MAX;j+=tmp){ 
set(j); 
} 
} 
} 
11 
int dem = 1; sum[1] = 2; 
for(int i=3; i<MAX; i+=2) 
if(!check(i)){ 
dem++; sum[dem] = sum[dem-1]+i; 
} 
} 
int main(){ 
 //freopen("","r",stdin); freopen("","w",stdout); 
 Era3(); 
 scanf("%d",&t); 
 for(int i=1;i<=t;i++){ 
scanf("%d",&n); 
printf("%d\n",sum[n]); 
 } 
 return 0; 
} 
Bài 3. Tìm số nguyên tố thứ N 
Biết dãy các số nguyên tố là: 2, 3, 5, 7, 11, 13, 
Bài toán đặt ra ở đây là cho một số nguyên dương N. Hãy cho biết giá trị của 
số nguyên tố thứ N trong dãy các số nguyên tố (thứ tự các số nguyên tố trong dãy 
các số nguyên tố bắt đầu từ 1) 
Dữ liệu vào: cho trong tệp có cấu trúc: 
- Dòng đầu tiên chứa số T là số lượng bộ tests (1 ≤ T ≤ 10
5
) 
- T dòng tiếp theo, mỗi dòng cha một số N (1 ≤ N ≤ 106). 
Kết quả ra: Ghi ra tệp gồm T dòng, mỗi dòng ghi một số tương ứng là giá trị của 
số nguyên tố thứ N cho trong tệp dữ liệu vào. 
Ví dụ: 
Dữ liệu vào Kết quả ra 
4 
6 
2 
5 
4 
13 
3 
11 
7 
12 
Hướng dẫn: Giá trị của số nguyên tố thứ N có thể lên đến 108. Vì vậy dùng 
sàng cải tiến để tạo trước mảng chứa các số nguyên tố. 
Code minh họa: 
#include 
using namespace std; 
#define MAX 100000000 
#define check(n) (prime[n>>6]&(1>1))) 
#define set(n) prime[n>>6]|=(1>1)) 
int pri[1000001],t,n; 
int prime[MAX>>6]; 
void Era3(){ 
for(int i=3;i*i<=MAX;i+=2){ 
if (!check(i)){ 
int tmp = 2*i; 
for(int j=i*i;j<=MAX;j+=tmp){ 
set(j); 
} 
} 
} 
int dem = 1; pri[1] = 2; 
for(int i=3; i<MAX; i+=2) 
if(!check(i)){ 
dem++; pri[dem] = i; 
} 
} 
int main(){ 
 //freopen("","r",stdin); freopen("","w",stdout); 
 Era3(); 
 scanf("%d",&t); 
 for(int i=1;i<=t;i++){ 
scanf("%d",&n); 
printf("%d\n",pri[n]); 
13 
 } 
 return 0; 
} 
Bài 4: Chú gấu Tommy và các bạn 
Chú gấu Tommy là một chú gấu rất dễ thương. Một ngày nọ chú đến trường 
và được thầy dạy về những con số nguyên tố. Chú và các bạn vô cùng thích thú và 
lao vào tìm hiểu chúng. Thế nhưng, càng tìm hiểu sâu chú lại càng gặp phải những 
bài toán khó về số nguyên tố. Hôm nay thầy giao cho cả lớp một bài toán khó và 
yêu cầu cả lớp ai làm nhanh nhất sẽ được thầy cho bánh. Vì thế, để có bánh ăn, 
Tommy phải giải bài toán nhanh nhất có thể. Bài toán như sau: 
Cho dãy n số nguyên dương x1, x2, , xn và m truy vấn, mỗi truy vấn được cho 
bởi 2 số nguyên li, ri. Cho một hàm f(p) trả về số lượng các số xk là bội của p. p S li ri
f 
p 
∑ , trong đó S(li,ri) là tập các số 
Câu trả lời cho truy vấn li, ri là tổng ( , )( ) 
nguyên tố trong đoạn [li,ri] 
Bạn hãy giúp chú gấu Tommy giải bài toán này nhé! 
Dữ liệu vào: file TOMMY.INP 
- Dòng đầu tiên chứa số nguyên n (1≤ n ≤ 105) 
- Dòng th 2 cha n số nguyên dương x1, x2, , xn (2 ≤ xi ≤ 107) 
- Dòng th 3 cha số nguyên m (1 ≤ m ≤ 50000). Mỗi dòng i trong m dòng 
sau chứa 2 số nguyên ngăn cách bởi 1 dấu cách li, ri (2 ≤ li ≤ ri ≤ 2.10
9) Kết 
quả ra: file TOMMY.OUT 
- Gồm m dòng, mỗi dòng 1 số nguyên là câu trả lời cho một truy 
vấn. Ví dụ: 
TOMMY.INP TOMMY.OU
T 
6 
5 5 7 10 14 15 
3 
2 10 
3 12 
4 4 
9 
7 
0 
Thời gian: 1s 
14 
Giải thích: 3 truy vấn trong test1 
1. Truy vấn 1: l = 2, r = 11. Ta cần tính: 
f(2) + f(3) + f(5) + f(7) + f(11) = 2 + 1 + 4 + 2 + 0 = 9. 
2. Truy vấn 2: l = 3, r = 12. Ta cần tính: f(3) + f(5) + f(7) + f(11) = 1 + 4 + 2 + 0 = 7. 
3. Truy vấn 3: l = 4, r = 4 không có số nguyên tố. 
Hướng dẫn: 
Cách 1: O(m.n.y) với y lá số lượng số nguyên tố trong đoạn [l,r] B1) Đọc 
file và xác định giá trị c[i] là số lần xuất hiện của giá trị i trong dãy số. B2) 
Dùng sàng Eratosthenes để xác định các số nguyên tố trong đoạn [1..10
7
] 
B3) Với mỗi truy vấn trong m truy vấn, ta lần lượt xét từng số nguyên tố i trong 
đoạn [li,ri]. 
- Với mỗi số nguyên tố i, ta duyệt lại mảng x và đếm số lượng bội của i là 
f(i); - Tổng các f(i) chính là kết quả cần tìm. 
Cách 2: O(max(m,n).y) 
B1) Tương tự cách 1 
B2) Dùng sàng số nguyên tố, kết hợp tính các giá trị f(i) (với i là số nguyên tố 
trong đoạn [1, 107) 
- Tính f(2)? f(2) = c[2]+ c[4] + c[6] + c[8],... 
- Tính f(5)? f(5) = c[5] + c[10]+ c[15] + c[20],... 
- Tính f(n)? f(n) = c[n] + c[2·n] + c[3·n] + c[4·n],... 
Ta thấy tư tưởng này rất giống với thuật toán sàng Eratosthenes. Vì vậy ta có thể 
dùng thuật toán sàng và chỉnh sửa lại. Kết quả tính sẽ được lưu trữ vào f[n] 
B3) Với mỗi truy vấn trong m truy vấn, ta lần lượt xét từng số nguyên tố i trong 
đoạn [li,ri]. Ta tính tổng các f(i) chính là kết quả cần tìm. 
Cách 3: O(max(m,n)) 
Để giải bài toán này ta cần giải quyết một số vấn đề sau: 
B1, 2) Tương tự cách 2 
B3) Bây giờ ta cần tính tổng tiền tố S của mảng num. Với S[i] = f[1] + f[2] + 
+f[i] 
B4) Sau khi tính tổng tiền tố xong, ta có thể tính toán tổng số lượng phần tử giữa l 
và r trong thời gian O(1), nghĩa là ta tính s[r] – s[l-1]. Bây giờ ta có thể đọc các 
truy vấn và trả lời chúng dễ dàng. 
Cần lưu ý là cận phải r có thể lớn hơn 107, vì vậy ta có thể giải r xuống chỉ còn 
10
7
 thôi và tất cả các số được cho đều bé hơn hoặc bằng 10
7. 
15 
Code 
#include 
using namespace std; 
#define MAX 10000001 
int prime[MAX]; 
long c[MAX], f[MAX]; 
long long sum[MAX]; 
long t,n,m; 
//FILE * fi = freopen("tommy.inp","r",stdin); 
//FILE * fo = freopen("tommy.out", "w", stdout); 
ifstream fi ("tommy.inp"); 
ofstream fo ("tommy.out"); 
//--------------------------- 
int eratosthene(){ 
for(long long i=2;i*i<=MAX; ++i){ 
if (!prime[i]){ 
for(long long j=i;j<=MAX;j+=i){ 
f[i] += c[j]; 
prime[j]=true; 
} 
} 
} 
return 0; 
} 
//------------------------------- 
void process(){ 
fi>>n; 
for(long i = 1; i<= n; ++i){ 
fi>>t; 
++c[t]; 
16 
} 
eratosthene(); 
for(long i = 2; i<= MAX ; ++i) 
sum[i] = sum[i-1] + f[i]; 
fi>>m; 
long li,ri; 
for (long i = 1; i<= m; ++i){ 
fi>>li>>ri; 
if (ri>1E7) ri = 1E7; 
fo<<sum[ri] - sum[li-1]<<'\n'; 
} 
} 
//--------------------------------- 
int main(){ 
ios_base::sync_with_stdio(false); 
process(); 
return 0; 
} 
Bài 5: Hoán đổi 
Trong giờ giải lao, do lớp vừa học xong các kiến thức về số nguyên tố, nên 
lớp trưởng của John đã suy nghĩ ra một trò chơi về dãy số cũng khá thú vị. Trò 
chơi như sau: 
Cho một dãy số a[1], a[2], ..., a[n], gồm các số nguyên phân biệt từ 1 đến n. 
Nhiệm vụ là ta phải sắp xếp các số theo thứ tự tăng dần theo qui tắc sau (có thể áp 
dụng nhiều lần): 
1. Chọn trong dãy số 2 chỉ số i, j (1 ≤ i < j ≤ n; (j - i + 1) là số 
nguyên tố) 2. Hoán đổi 2 số tại vị trí i, j. 
Không cần thiết phải sử dụng số lần nhỏ nhất các qui tắc trên, nhưng không 
được sử dụng vượt quá 5*n lần. 
Input: vào từ file HOADOI.INP như sau: 
- Dòng đầu tiên chứa số nguyên n (1 ≤ n ≤ 105) 
- Dòng tiếp theo cha n số nguyên phân biệt a[1], a[2], ..., a[n] 
(1 ≤ a[i] ≤ n). Output: ghi ra file HOANDOI.OUT như sau: 
17 
- Dòng đầu tiên, in số nguyên k (0 ≤ k ≤ 5n) là số lần qui tắc được sử dụng. 
- Dòng tiếp theo in k cặp (i,j) đã hoán đổi. Với i,j thỏa yêu cầu đề bài. Nếu 
có nhiều đáp án ta in một đáp án bất kỳ. 
Ví dụ: 
HOADOI.INP HOANDOI.OUT 
3 
3 2 1 
1 
1 3 
2 
1 2 
0 
4 
4 2 3 1 
3 
2 4 
1 2 
2 4 
Thuật toán: O(n+m) với m là số lần hoán đổi 
Ý tưởng duyệt: với mỗi số i chưa đúng vị trí, gọi y[i] là vị trí hiện tại của số 
i. Ta tìm vị trí t phù hợp lần lượt từ vị trí thứ i, i+1, i+2 Khi tìm được t ta hoán 
đổi 2 giá trị tại y[i] và t, ghi nhận vị trí mới. làm tương tự cho đến khi tất cả các số 
đều đúng vị trí. 
Nhận xét: với mỗi số i ta đã tìm vị trí xa nhất thỏa yêu cầu để hoán đổi nên 
có thể thấy đây là thuật toán tốt. Thực tế cài đặt cho thấy số lần hoán đổi thỏa yêu 
cầu đề bài. 
Chi tiết thuật toán: 
1. Khi đọc dãy số ta tiến hành lưu lại vị trí của từng số a[i] ban đầu là y[a[i]] = 
i 2. Xét từng số i = 1, 2, 3, , n. Với mỗi số ta thực hiện nhiều lần các bước 
sau: 
a. Gọi j = y[i] là vị trí hiện tại của số i trong dãy số. Trong khi j>i (i chưa đúng 
chỗ), ta thực hiện tìm vị trí t thích hợp để hoán đổi giá trị i với t = i, i+1, i+2,  
b. Khi tìm được vị trí t phù hợp, ta thực hiện đếm số lần hoán đổi và cập nhật vị 
trí như sau 
- y[a[t]] = j 
- y[a[j]] = t 
c. Hoán đổi a[t] và a[j] 
Code tham khảo: 
#include 
using namespace std; 
#define check(n) (prime[n>>6]&(1>1))) 
#define set(n) prime[n>>6]|=(1>1)) 
18 
#define MAX 100000000 
long y[100000005],c=0,a[100000005],n,t,j; 
vector > v; 
int prime[MAX>>6]; 
//------------------- 
void eratos(){ 
 for (long i=3;i*i<=MAX;i+=2) 
 if (!check(i)){ 
 long t=2*i; 
 for (long j = i*i; j<= MAX; j+=t) 
 set(j); 
 } 
} 
//-------------------- 
bool checkprime(long m){ 
 if ((m==1)||((m>2)&&(!(m%2)))||((m%2)&&check(m))) return false; 
return true; 
} 
void process(){ 
 FILE * fi = freopen("swap.inp","r", stdin); 
 FILE * fo = freopen("swap.out","w", stdout); 
 scanf("%d",&n); 
 eratos(); 
 for (long i =1; i<=n; i++){ 
 scanf("%d",&a[i]); 
 y[a[i]] = i; 
 } 
 for (long i=1;i<=n;i++) 
 { 
 for (j=y[i];j>i;) 
 { 
19 
 t=i; 
 while (!checkprime(j-t+1)) 
 t++; 
 c++; 
 y[a[t]]=j; 
 y[a[j]]=t; 
 v.push_back(make_pair(t,j)); 
 swap(a[t],a[j]); 
 j=t; 
 } 
 } 
 cout<<c<<'\n'; 
 for (long i=0;i<c;i++) 
 cout<<v[i].first<<" "<<v[i].second<<'\n'; 
} 
int main() 
{ 
 ios_base::sync_with_stdio(false); 
 process(); 
 return 0; 
} 
Bài 6: Thuyền trưởng Prime 
Thuyền trưởng Prime đang đi thám hiểm đến vùng đất bí ẩn giữa đại dương 
mênh mông cùng với quân đoàn tinh nhuệ nhất của ông ta. Trên đường đi có rất 
nhiều thế lực đen tối tấn công vào tinh thần của các binh sĩ. Chúng làm cho binh sĩ 
hoảng loạn không làm chủ được bản thân. Vì thế, ông đã quyết định ném một số 
binh sĩ xuống biển. Các binh sĩ có bị ném xuống biển hay không tùy thuộc vào số 
hiệu họ mang trên người. 
Con tàu được chia thành 3 phần: LEFT, RIGHT và CENTRAL. Mỗi binh sĩ 
trên tàu được gắn một số hiệu nhận dạng (id). Và theo số id đó họ sẽ làm việc trên 
một phần của con tàu. Khu vực làm việc được qui định như sau đối với một binh 
sĩ: Các binh sĩ được sắp làm việc phải có số id là số nguyên tố và không chứa số 0. 
Ngoài ra từng khu vực sẽ có qui định riêng đối với binh sĩ như sau: 
+ Khu vực CENTRAL: anh ta sẽ làm việc ở phần giữa của con tàu nếu: 
20 
- Khi bỏ dần các chữ số bên trái của id lần lượt theo thứ tự thì số còn lại cũng 
phải là số nguyên tố. 
- Tương tự cho các số nằm bên phải của số id. 
VD: Xét số id = 3137, sẽ làm việc ở khu vực giữa vì ta có các số 3137, {313, 
31, 3}, {137, 37, và 7} đều là số nguyên tố. 
+ Khu vực LEFT: anh ta sẽ làm việc ở phần trái của con tàu nếu: 
- Khi bỏ dần các chữ số bên trái của id lần lượt theo thứ tự thì số còn lại cũng 
phải là số nguyên tố. 
VD: Xét số id = 1367, sẽ làm việc ở khu vực trái vì ta có các số 1367, 367, 
67, và 7 là các số nguyên tố. 
+ Khu vực RIGHT: anh ta sẽ làm việc ở phần phải của con tàu nếu: 
- Khi bỏ dần các chữ số bên phải của id lần lượt theo thứ tự thì số còn lại cũng 
phải là số nguyên tố. 
VD: Xét số id = 2333, sẽ làm việc ở khu vực phải vì ta có các số 2333, 233, 
23, và 2 là các số nguyên tố. 
+ DEAD: Binh sĩ bị ném xuống sông là binh sĩ không làm việc ở bất cứ phần nào 
của con tàu. 
Dữ liệu vào: cho trong tệp có cấu trúc: 
- Dòng đầu tiên chứa số nguyên T, là số binh sĩ trên con tàu (2 ≤ T ≤ 10
3
) 
- T dòng tiếp theo, mỗi dòng chứa một số id của mỗi binh sĩ (1 ≤ id ≤ 
108) 
Kết quả ra: ghi ra tệp gồm T dòng, mỗi dòng ghi CENTRAL hoặc LEFT hoặc 
RIGHT hoặc DEAD tương ứng vị trí làm việc của các binh sĩ hoặc bị ném xuống 
biển. 
Ví dụ: 
Dữ liệu vào Kết quả ra 
5 
3137 
1367 
2333 
101 
12 
CENTR
AL 
LEFT 
RIGHT 
DEAD 
DEAD 
Hướng dẫn: Với số id có thể đến 10
8
. Vì vậy có thể dùng sàng cải tiến để giải bài 
tập này. 
Code tham khảo: 
#include 
using namespace std; 
21 
#define MAX 100000000 
#define check(n) (prime[n>>6]&(1>1))) 
#define set(n) prime[n>>6]|=(1>1)) 
int prime[MAX>>6]; 
int n; 
long a,label[50]; 
void eratos(){ 
 for (long i=3;i*i<=MAX;i+=2) 
 if (!check(i)){ 
 long t=2*i; 
 for (long j = i*i; j<= MAX; j+=t) 
 set(j); 
 } 
} 
bool checkprime(long y){ 
 if((y==1)||((y>2)&&(!(y%2)))||((y%2)&&check(y))) return false; 
return true; 
} 
int check_label(long m){ 
 string s,tmp; 
 stringstream stream; 
 stream << m; 
 s = stream.str(); 
 int tam = s.find('0'); 
 if (tam>0) return 4;//neu id chua so 0 
 //Bo lan luot cac so ben trai va kiem tra 
 bool f1 = true; 
 for(int i=1;i<s.length(); ++i){ 
 tmp = s.substr(i);//tao xau con khi bo i ky tu trai 
long x = atol(tmp.c_str()); 
 if (!checkprime(x)){ 
22 
 f1=false; 
 break; 
 } 
 } 
 //Bo lan luot cac so ben phai va kiem tra 
 bool f2 = true; 
 for(int i = 1; i<s.length(); ++i){ 
 tmp = s.substr(0,s.length()-i);//tao xau con khi bo i ky tu phai 
long x = atol(tmp.c_str()); 
 if (!checkprime(x)){ 
 f2 = false; 
 break; 
 } 
 } 
 if (f1 && f2) return 1;//central 
 else if (f1) return 2;//left 
 else if (f2) return 3;//right 
 else return 4;//dead 
} 
void process(){ 
 FILE* fi = freopen("captain.inp","r",stdin); 
 FILE* fo = freopen("captain.out","w",stdout); 
 eratos(); 
 scanf("%d",&n); 
 for (int i=0; i<n; ++i){ 
 scanf("%ld", &a); 
 if (!checkprime(a)) label[i] = 4; 
 else label[i] = check_label(a); 
 } 
 //in ket qua 
 for (int i=0; i<n; ++i){ 
23 
 if (label[i]==1) printf("%s\n","CENTRAL"); else if 
(label[i] == 2) printf("%s\n","LEFT"); else if(label[i] 
== 3) printf("%s\n", "RIGHT"); else printf("%s\n", 
"DEAD"); } 
} 
int main() 
{ 
 process(); 
 return 0; 
} 
24 
III. KẾT LUẬN 
Với khả năng và kinh nghiệm có hạn, trong sáng kiến này tôi đã trình bày các 
cải tiến của sàng nguyên tố Eratosthenes nhằm áp dụng có hiệu quả đối với một số 
bài toán có liên quan đến việc đếm, liệt kê hay kiểm tra nhiều số nguyên tố trong 
phạm vi đến 10
8 
mà sàng Eratosthenes cơ bản không đáp ứng được. 
Mặc dù số lượng ví dụ bài tập áp dụng được trình bày còn ít, tuy nhiên qua đó 
đã cho thấy hiệu quả của việc cải tiến sàng Eratosthenes cũng như giúp học sinh 
xác định những bài tập cần áp dụng sàng cải tiến để giải quyết. 
Tuy nhiên, thực tế vẫn có một cách cải tiến khác để đạt được các giới hạn N 
lớn hơn trong thời gian 1s nhưng cài đặt khá phức tạp như: 
Ta có thể cải tiến tiếp thuật toán Eratosthenes theo đoạn (Segmented sieve of 
Eratosthenes) rất hay. Tuy nhiên, thuật toán cài đặt phức tạp hơn và dành cho các 
CPU thế hệ mới, khi mà bộ nhớ đệm (Cache L1) có dung lượng lớn. Kết quả đem 
lại là rất tốt với N = 109. Ta có thể tham bài viết theo cách này tại link sau: 
https://primesieve.org/segmented_sieve.html 
Bên cạnh đó, việc áp dụng phương pháp Wheel factorization để cải tiến sàng 
Eratosthenes cũng là một hướng cải tiến khác cho hiệu quả tốt. Thống kê trên wiki: 
https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes 
Ta cũng có thể kết hợp sàng Eratosthenes cơ bản với thuật toán Meissel – 
Lehmer sẽ đem lại kết quả khoảng N = 10
9
, nếu CPU mạnh có thể đạt đến 10
10
. 
Tuy nhiên, cách cài đặt là khá phức tạp và chủ yếu dùng để đếm số lượng số 
nguyên tố chứ chưa thể liệt được hết các số nguyên tố. Không phù hợp cho các bài 
toán cần đến giá trị của từng số nguyên tố. 
Trên đây chỉ là một kinh nghiệm nhỏ của bản thân được rút ra qua quá trình 
giảng dạy và tự học. Chắc chắn còn nhiều hạn chế, rất mong nhận được những góp 
ý của quý thầy cô! 
Thanh Chương, ngày 10 tháng 3 năm 2021 
XÁC NHẬN CỦA 
THỦ TRƯỞNG ĐƠN VỊ 
Tôi xin cam đoan đây là SKKN của 
mình viết, không sao chép của người 
khác. 
Nguyễn Quang Tuấn
25 
TÀI LIỆU THAM KHẢO 
1. 
https://en.wikipedia.org/wiki/Meissel%E2%80%93Lehmer_algorithm 
2.  
3. https://sites.google.com/site/kc97ble/arithmetic/lehmer---dhem-so-luong-so 
nguyen-to-nho-hon-n 
26