Sàng nguyên tố trong thời gian tuyến tính

SÀNG NGUYÊN TỐ TUYẾN TÍNH

Cấu trúc dữ liệu int uocso[...]
Lúc đầu cho uocso[i] = 0 với uy ước uocso[i] = 0 thì i là số nguyên tố.
Sau đó:
- Nếu uocso[i] = 0 tức là i là số nguyên tố ta gán uocso[i] = i, nghĩa là i là số nguyên tố nên ước số của i là số i
- Nếu uocso[i] = k thì ước số nguyên tố nhỏ nhất của i là k

Nhận xét: sau khi chạy xong thuật toán thì có thể dùng mảng uocso[] theo 2 cách:
Cách 1: Dùng để kiểm tra số nguyên i có là số nguyên tố không: nếu uocso[i]=i thì i là số nguyên tố
Cách 2: Dùng để biết số nguyên tố nhỏ nhất của hợp số i là bao nhiêu, từ đó dùng để phân tích nhanh số nguyên i ra thành các thừa số nguyên tố

Cấu trúc dữ liệu vector<int> primes
primes dùng để chứa các số nguyên tố

Thuật toán: 
Xét từng số i từ 2 đến N
  - Nếu i là số nguyên tố thì: thêm i vào primes và cho uocso[i]=i
  - Xét các số nguyên tố đã lưu trong mảng primes và số nguyên tố này nhỏ hơn hay bằng ước số nguyên tổ nhỏ nhất của số i (tức là số nguyên tố lưu trong uocso[i]):
     + Bỏ đi các bội i là i*primes[j] hay ghi nhận uocso[i*primes[j]] là primes[j]



Chương trình:
const int N = 32000000
vector<int> primes;
int uocso[N];

void Sang() {
  for (int i=2; i<=N; i++) {
    if (uocso[i] == 0) {
      uocso[i] = i;
      primes.push_back(i);
    }

    for (int j=0; j<primes.size() && 
                  primes[j]<=uocso[i] && 
                  i*primes[j]<=N; j++)
      uocso[i*primes[j]] = primes[j];
  }
}