Minh họa sàng nguyên tố

Định nghĩa số nguyên tố
Số nguyên tố là số nguyên dương có duy nhất 2 ước phân biệt là 1 và chính nó. Số nguyên tố nhỏ nhất là số 2.
Ý tưởng của thuật toán sàng nguyên tố Eratosthenes
Dựa theo lý thuyết về số nguyên tố: Một số nguyên tố là số chỉ có 2 ước là 1 và chính nó. Do vậy, nếu ta xác định được số x là số nguyên tố, ta có thể kết luận mọi số chia hết cho x đều không phải số nguyên tố. Do đó ta đã loại bỏ được rất nhiều số mà không cần kiểm tra.
Ví dụ:
Số 2 là số nguyên tố => các số 4, 6, 8, 10, ... không phải số nguyên tố.
Số 3 là số nguyên tố => các số 9, 15, 21, ... không phải số nguyên tố. (Do 6, 12, 18 đã bị loại ở số 2)
Thuật toán sàng nguyên tố Eratosthenes
Tạo mảng đánh dấu cho tất cả các phần tử từ 2 đến N và mặc định tất cả đều là số nguyên tố
Xét số đầu tiên tìm được là số nguyên tố – giả sử x, đánh dấu tất cả các bội của x: 2x, 3x, 4x,… trong đoạn [x, N] không phải số nguyên tố.
Tìm số tiếp theo được đánh dấu là số nguyên tố trong [x, N]. Nếu không còn số nào, thoát chương trình. Nếu còn, gán nó bằng x và lặp lại bước 2.
Khi kết thúc giải thuật, các số không bị đánh dấu là các số nguyên tố.

Cài đặt thuật toán sàng nguyên tố
- C++

#include <iostream>
using namespace std;
int main()
{
    int N = 1000;
    bool check[N + 1];
    //Danh dau tat ca cac so tu 2 den N deu la so nguyen to
    for (int i = 2; i <= N; i++)
    {
        check[i] = true;
    }
//Xet tu so dau tien tim duoc la so nguyen to, voi moi so tim duoc thi boi cua no khong phai la so nguyen to
    for (int i = 2; i <= N; i++)
    {
        if (check[i] == true)
        {
            for (int j = 2 * i; j <= N; j =j+ i)
            {
                check[j] = false;
            }
        }
    }
    //In ra cac so nguyen to tim duoc
    for (int i = 2; i <= N; i++)
    {
        if (check[i] == true)
        {
            cout<<i<<" ";
        }
    }
    return 0;
}

- Java

import java.util.*;import java.lang.*;import java.io.*;/* Name of the class has to be "Main" only if the class is public. */class Eratosthenes {  public static void main (String[] args) throws java.lang.Exception {    int N = 1000;    boolean[] check = new boolean[N + 1];    // Khởi tạo tất cả các số [2...N] đều là số nguyên tố    for (int i = 2; i <= N; i++) {      check[i] = true;    }    // Thuật toán sàng nguyên tố    // Nếu một số là số nguyên tố, thì tất cả các bội của nó không phải số nguyên tố    for (int i = 2; i <= N; i++) {      if (check[i] == true) {        for (int j = 2 * i; j <= N; j += i) {          check[j] = false;        }      }    }    // In ra các số là số nguyên tố    for (int i = 2; i <= N; i++) {      if (check[i] == true) {        System.out.print(i + " ");      }    }  }}