# Cải tiến sàng nguyên tố Eratosthenes

Ta đã biết đến sàng nguyên tố Eratosthenes và các nguyên lý của nó. Với giới hạn thời gian là 1 giây và giới hạn bộ nhớ là 64MB, ta có thể tạo một sàng nguyên tố khoảng $6*10^7$ phần tử. Nhưng có một cách giải quyết khác, với thời gian và bộ nhớ tương tự, nhưng có thể làm được 3 lần hơn thế. Chúng ta hãy cùng tìm hiểu nhé.

## $6k+1$ và $6k+5$

Ta biết rằng một số nguyên tố, ngoại trừ $2$ và $3$, luôn luôn nguyên tố cùng nhau với $6$, do đó những số nguyên tố này luôn có dạng $6k+1$ và $6k+5$. Ta sẽ vận dụng tính chất này để cải tiến sàng nguyên tố.

### Tại sao lại là $6k+1$ và $6k+5$?

Thực tế, có một số khác cũng có tính chất tương tự, đó là số $4$, với $4k+1$ và $4k+3$. Nhưng tính chất $6k+1$ và $6k+5$ mạnh hơn khá nhiều so với $4k+1$ và $4k+3$. Thêm nữa, chỉ có hai số nguyên nhỏ hơn $6$ và nguyên tố cùng nhau với $6$, do đó số trường hợp sẽ được giảm đi nhiều.

## $6k+5$

Đầu tiên, ta xét các số có dạng $6k+5$. Ta thấy rằng một hợp số có dạng $6k+5$ luôn tồn tại một ước nguyên tố có dạng $6k+5$, do đó ta áp dụng ý tưởng của sàng Eratosthenes, nhưng với những số có dạng $6k+5$.

Thêm nữa, ta nhận thấy một số có dạng $6k+5$ chỉ có thể là tích của một cặp số có dạng $(6u+5, 6v+1)$. Do đó, khi tìm được một số nguyên tố $p = 6x+5$, ta sẽ chỉ cần loại bỏ những số là tích của $p$ và một số nguyên dạng $6k+1$.

Ví dụ, đê tìm ra các số nguyên tố nhỏ hơn $100$ có dạng $6k+5$, ta có thể làm như sau:

- Đầu tiên, ta có $6*0+5=5$ chưa bị loại bỏ, vậy nó là số nguyên tố. Ta loại bỏ các số $5*7=35$, $5*13=95$, đều là các tích của $5$ và một số có dạng $6k+1$.
- Tiếp theo, ta có $6*1+5=11$ chưa bị loại bỏ, vậy nó là số nguyên tố. Ta loại tiếp $11*7=77$.
- Tiếp theo nữa, ta có $6*2+5=17$ chưa bị loại bỏ. Nhưng ta có $17*7=119>100$, do đó, từ những số từ $17$ trở lên, ta sẽ không loại thêm được một số nào nữa.
- Vậy, tất cả các số nguyên dương có dạng $6k+5$ bé hơn $100$, loại đi $35, 95$ và $77$, đều là những số nguyên tố.

## $6k+1$

Trường hợp $6k+1$ thì có chút phức tạp hơn, nhưng ta hoàn toàn có thể phân tích được một hợp số có dạng $6k+1$ vào hai trường hợp sau:

- $6k+1=(6u+5)*(6v+5)$
- $6k+1=(6m+1)*(6n+1)$

Với trường hợp đầu tiên, ta có thể khéo léo chọn $u$ sao cho $6u+5$ là ước nguyên tố nhỏ nhất có chia 6 dư 5 của $6k+1$, nên ta chắc chắn được rằng $v\ge u$, do đó, khi xét một số nguyên tố ở sàng nguyên tố $6k+5$, ta sẽ quét hết tất cả những trường hợp $6v+5$ có thể xảy ra và đánh dấu $(6u+5)*(6v+5)$ không phải hợp số ở sàng $6k+1$. Với trường hợp thứ hai ta làm tương tự như sàng $6k+5$.