Sàng Eratosthenes

Eratosthenes

Sàng Eratosthenes là một thuật giải toán cổ xưa để tìm các số nguyên tố nhỏ hơn 100. Thuật toán này do nhà toán học cổ Hy Lạp là Eratosthenes (Ơ-ra-tô-xten) "phát minh" ra.

Hình thức của sàng Eratosthenes

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.^{[cần dẫn nguồn]}

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.

Công thức

Theo thuật ngữ toán, ta có thể tìm các số nguyên tố bằng sàng Eratosthenes như sau:

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ố
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ố

• 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ố.

Và đây là giải thuật: void primeLessN ( int n) {

    bool prime[n];
    int j, temp;
    prime[0] = prime[1] = false;
    for ( temp = 2; temp < n; temp++)
        prime[temp] = true;
    for ( j = 2; 2*j < n; j++)
        prime[2*j] = false;
    int p = 3;
    while ( p <= n/2)
          {
              for ( j = p; p*j < n; j++)
              prime[p*j] = false;
              do ++p;
              while ( !prime[p]);
              }
    for ( temp = 2; temp < n; temp++)
        if (prime[temp]) cout << temp << " ";
    }
    

int main() {

   primeLessN ( 18);
   system ("pause");
   return 0;
   }