Sàng nguyên tố trên đoạn [L, R]

SÀNG NGUYÊN TỐ TRÊN ĐOẠN [L, R]

Bài toán: Hãy tìm các số nguyên thuộc đoạn [L, R], trong đó (1<=L<=R<=2.000.000.000 và R-L<=1.000.000).

Thuật toán:
- Trường hợp 1. Nếu R<=1.000.000 thì áp dụng phương pháp sàng bình thường
- Trường hợp 2. Nếu R>1.000.000 thì ta có có nhận xét

Nhận xét: nếu số nguyên n không là số nguyên tố thì n có ước số là sqrt(n).
Trong trường hợp n là số lớn nhất như trong đề bài, tức là n=2.000.000.000 thì n có ước số nhỏ hơn hay bằng sqrt(n)=44.722. Vậy ta sẽ tìm các số nguyên tố nhỏ hơn hay bằng 44.722


Bước 1. Sàng các số nguyên tố trên đoạn [1...44.722], để cho gọn gàng ta có thể sàng trên đoạn [1...50.000], còn nếu chính xác thì ta chỉ cần sàng trên đoạn [1...sqrt(R)]
Bước 2. Xét các số nguyên tố i trong đoạn [1...sqrt(R)], ta sẽ loại bỏ đi các số không nguyên tố j là bội của i. Nhưng để cho nhanh ta phải tính toán sao cho j thuộc [L, R]

Cách tính j:
- Nếu L chia hết cho i thì j=L
- Nếu L không chia hết cho i thì:
  + Tìm số lớn nhất gần L mà chia hết cho i, tức là ta lấy số L trừ đi phần dư khi chia L cho i: k=L-(L%i). Lúc này k chia hết cho i.
  + Vậy j = k+i sẽ là số lớn hơn L và chia hết cho i

Cách đánh dấu đoạn [L, R]:
- Vì L, R có thể lên đến 2 tỷ, nhưng đoạn từ L đến R chỉ có tối đa 1 triệu số nên ta ánh xạ đoan [L, R] sang đoạn [0, R-L]

#include <bits/stdc++.h>
using namespace std;

bitset<1000000+10> isSmallPrime;
bitset<1000000+10> isLargePrime;

vector<int> primes;

void SangTrenDoan(int L, int R) {
  // Buoc 1: Sang các số nguyên tố <= sqrt(R)
  int n = (int) sqrt(R);
  isSmallPrime.set(); isSmallPrime[0]=isSmallPrime[1]=false;
  for (int i=4; i<=n; i+=2) isSmallPrime[i]=false;

  for (int i=3; i*i<=n; i+=2)
    if (isSmallPrime[i])
      for (int j=i*i; j<=n; j+=i) isSmallPrime[j]=false;

  // Bước 2: Sang các số nguyên tố thuộc đoạn [L, R]
  isLargePrime.set();
  for (int i=2; i*i<=R; i++)
    if (isSmallPrime[i]) {
      if (L%i==0) 
        for (int j=L; j<=R; j+=i) isLargePrime[j-L]=false;
      else if (L>i) {
        int du = L%i;
        for (int j=(L-du)+i; j<=R; j+=i) isLargePrime[j-L]=false;
      }
    }
   
  for (int i=L; i<=R; i++)
    if (isLargePrime[i-L]) primes.push_back(i);
}