Bài 2. Số nguyên tố bị thiếu (MISSINGPRIME)

🔗 Problem: [HSG_Số Học]. Bài 2. Số nguyên tố bị thiếu (MISSINGPRIME)

Linear sieve

const int limN = 1e6 + 5;
int lp[limN]; // lp[i] = ước nguyên tố nhỏ nhất của i
vector<int> primes;

//lp[i] == 0 => i là nguyên tố => số nguyên tố bé nhất trong phân tích của i nó là i
//lp[i] != 0 => i là hợp số

void linear_sieve() {
    for(int i = 2; i <= limN; i++) {
        if(!lp[i]) { // khi gặp số nguyên tố mới
            lp[i] = i; // ước nguyên tố nhỏ nhất của i chính là i
            primes.pb(i); // thêm i vào danh sách số nguyên tố
        }
        for(int j = 0; j < sz(primes) && i * primes[j] <= limN; j++) { // generate ra các hợp số tạo bởi các số nguyên tố bé hơn pr[i]
            lp[i * primes[j]] = primes[j];
            if(primes[j] == lp[i]) break;
        }
    }
}

Mã giải (C++)

main.cpp