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.

1. Kiểm tra xem một số có phải số nguyên tố hay không?

• Nếu số đó bé hơn \(2\), kết luận không phải số nguyên tố.
• Đếm số ước của \(x\) trong đoạn từ \(2\) đến căn bậc hai của \(x\). Nếu \(x\) không có ước nào trong đoạn từ \(2\) đến căn bậc hai của x thì nó là số nguyên tố. Ngược lại thì không phải. Như vậy, nếu bạn đếm từ \(1\) thay vì \(2\) thì \(x\) là số nguyên tố khi ta đếm được \(1\) ước số trong đoạn từ \(1\) đến căn bậc hai của \(x\).

Tại sao lại chỉ đếm các ước trong đoạn từ \(2\) đến \(\sqrt{x}\)?

• Nếu bạn để ý thì một số nguyên \( \geq 2\) bất kỳ sẽ luôn có số ước ở nửa đầu căn bậc hai của nó bằng số ước ở nửa sau căn bậc hai của nó. Cụ thể, các ước sẽ phân bố thành hai miền từ \([2; sqrt(x)]\) và từ \([sqrt(x); x]\).
• Chú ý: Khi kiểm tra bạn nhớ phải là \(\le sqrt(n)\) nhé. Nếu chỉ để dấu nhỏ hơn thì các số chính phương như \(4, 9\) sẽ là số nguyên tố đấy. Tại sao thì bạn thử giải thích xem nào ? Vậy thuật toán có độ phức tạp \(O(sqrt(n))\).

Code kiểm tra số nguyên tố

bool isPrime(int n){
    if(n < 2) return false;
    for(int i = 2; i <= sqrt(n); i++)
        if(n % i == 0) return false;
    return true;
}

2. Thuật toán sàng nguyên tố Eratosthenes

Sàng nguyên tố Eratosthenes là một thuật toán giúp bạn nhanh chóng liệt kê các số nguyên tố. Đây là một thuật toán tìm số nguyên tố tối ưu khi muốn tìm tất cả các số nguyên tố nhỏ hơn một số \(N\) cho trước \((N \le 2)\). Vì đơn giản là số nguyên tố nhỏ nhất là \(2\) mà.

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\))

Mô tả thuật toán

• Bước \(1\): 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ố
• Bước \(2\): 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 ước của \(x: 2x, 3x, 4x,… \)trong đoạn \([x, N]\) không phải số nguyên tố. Trong thực tế, ta chỉ cần đánh dấu các số \( x*x, (x+1)x, (x+2)x…\) trong đoạn \([x*x,N]\) không phải là số nguyên tố. Vì các số \(2x,3x,4x,…(x-1)x\) đã bị loại bởi các số nguyên tố bé hơn \(x\) (vì nó có ước là \(2,3,4,5…\))
• Bước 3: 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\).
• Bước 4: 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ố

Code sàng nguyên tố

#define MAXN 1000000

bool check[MAXN+1];

void sangNguyenTo() {

  // Khởi tạo tất cả các số [2...MAXN] đều là số nguyên tố
  for (int i = 2; i <= MAXN; 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 <= sqrt(MAXN); i++) {
    if (check[i] == true) {
      for (int j = i * i; j <= MAXN; j += i) {
        check[j] = false;
      }
    }
  }
  // In ra các số là số nguyên tố
  for (int i = 2; i <= MAXN; i++) {
    if (check[i] == true) {
      printf("%d ", i);
    }
  }
}

Kết quả sau khi chạy

Các số nguyên tố từ 2 đến \(MAXN\) được liệt kê:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109...

Kết luận

Thuật toán sàng nguyên tố Eratosthenes có thời gian chuẩn bị trước mảng check là \(O(MAXN * logMAXN)\). Thời gian để kiểm tra \(1\) số trong khoảng \(2..MAXN\) là \(O(1)\).

3. Luyện tập

Đây là một số bài tập luyện tập sàng nguyên tố trong sách Competitive Programming Basic của Code Dream, đăng ký mua ngay để được luyện tập nhiều dạng bài về thuật toán khác, chấm bài online tại http://oj.codedream.edu.vn