Số nguyên tố luân phiên (Alternate Primes) đến N trong C++

In các số nguyên tố luân phiên (cách nhau một) đến N. Ví dụ N=15: số nguyên tố {2,3,5,7,11,13} → luân phiên {2,5,11}.

Thuật toán (Sieve of Eratosthenes + lọc luân phiên)

1. Tạo mảng boolean prime[0..N], khởi tạo true.
2. Sàng Eratosthenes: đánh dấu bội số của mỗi số nguyên tố.
3. Duyệt 2..N, in số nguyên tố luân phiên (dùng flag toggle).

Code ví dụ

#include <iostream>
#include <vector>
using namespace std;

void printAlternatePrime(int n) {
    vector<bool> prime(n + 1, true);
    prime[0] = prime[1] = false;
    
    // Sieve of Eratosthenes
    for (int p = 2; p * p <= n; p++) {
        if (prime[p]) {
            for (int i = p * 2; i <= n; i += p)
                prime[i] = false;
        }
    }
    
    // In luân phiên
    bool printFlag = true;
    cout << "So nguyen to lua phien: ";
    for (int p = 2; p <= n; p++) {
        if (prime[p]) {
            if (printFlag) {
                cout << p << " ";
                printFlag = false;
            } else {
                printFlag = true;
            }
        }
    }
    cout << endl;
}

int main() {
    int n;
    cout << "Nhap gioi han N: ";
    cin >> n;
    printAlternatePrime(n);
    return 0;
}

Kết quả

Nhap gioi han N: 20
So nguyen to lua phien: 2 5 11 17

Độ phức tạp

• Sieve: O(N log log N) thời gian, O(N) không gian.
• Lọc luân phiên: O(N).
• Tổng: O(N log log N).

Tối ưu cho N lớn (Segmented Sieve)

Nếu N > 10⁷, dùng Segmented Sieve chia thành các đoạn để tiết kiệm bộ nhớ.

Mở rộng: In index của số nguyên tố luân phiên

int idx = 0;
for (int p = 2; p <= n; p++) {
    if (prime[p]) {
        if (idx % 2 == 0) cout << p << " "; // 0-based: 0,2,4...
        idx++;
    }
}