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);
}
