Sàng nguyên tố O(n)

Bài toán: Tìm các số nguyên tố từ 2 đến n.

Cách tiêu chuẩn để giải bài toán này là sử dụng sàng nguyên tố Eratosthenes, cài đặt rất đơn giản, nhưng độ phức tạp là O(nlog(log(n))).

Sau đây xin giới thiệu một thuật toán cải tiến với độ phức tạp O(n).

Tư tưởng thuật toán

Nhận thấy rằng mọi số k đều có một cách biểu diễn duy nhất dưới dạng:k=lp[k]*x

với lp[k] là ước nguyên tố nhỏ nhất của k. Do đó lp[k] \leq lp[x]

Nếu thay lp[k] bằng số nguyên tố j \leq lp[x]:lp[j*x]=min(lp[j],lp[x])=j

Vì chỉ có một cách biểu diễn duy nhất nên lp[j*x] chỉ được tính 1 lần.

Nhận xét này giúp ta tính được mảng lp[i] cho mọi số i trong khoảng [2;n] với độ phức tạp O(n).

Code

Duyệt từ 2 đến n. Xét lp[i] có hai trường hợp xảy ra như sau:

  • Nếu lp[i]>0. Xét các số nguyên tố P \leq lp[i], gán lp[P*i]=P
  • Nếu lp[i]=0 dẫn tới i là số nguyên tố nên ta gán lp[i]=i. Lúc này lp[i] đã dương, ta làm như trường hợp trên.
using namespace std;

const int maxN = int(1e8)+111;

int pr[maxN], lp[maxN];
int prNum, N;

void PrimeSieve() {
    for(int i = 2; i <= N; i++) {
        if (lp[i] == 0) lp[i] = pr[prNum++] = i;
        int j = 0;
        while (j < prNum && pr[j] <= lp[i] && pr[j]*i <= N) {
            lp[pr[j]*i] = pr[j];
            j++;
        }
    }
}

Chứng minh độ phức tạp O(n)

Giả sử tồn tại một số A=P*i được duyệt qua nhiều hơn một lần. Lúc này ta sẽ có A=P_{1}*i=P_{2}*j với i khác j.
P_{1}P_{2} như đã nói ở trên là ước nguyên tố nhỏ nhất của A
\Rightarrow P_{1} = P_{2}
P_{1}=P_{2}P_{1}*i=P_{2}*j
\Rightarrow i=j (vô lý ngược với giả thuyết ban đầu)
Như vậy mỗi số A chỉ được duyệt qua một lần.

Tham khảo

Comment

avatar
  Subscribe  
Notify of