Tích của mỗi số nguyên tố thứ K trong mảng trong C++

Đề bài

Cho mảng các số nguyên tố và số K. Tính tích của các số nguyên tố nằm ở vị trí thứ K, 2K, 3K... trong mảng (1-based).

Ví dụ: arr={3,5,7,11,13}, K=2 → vị trí 2,4: 5 và 11 → tích = 55.

Thuật toán

1. Tạo sàng Eratosthenes để kiểm tra số nguyên tố nhanh (nếu mảng không đảm bảo toàn số nguyên tố).
2. Duyệt mảng, đếm số nguyên tố gặp được. Khi đếm đạt K → nhân vào kết quả, reset đếm.

Ví dụ minh họa (C++)

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

const int MAX = 1000000;
bool isPrime[MAX + 1];

void sieve() {
    fill(begin(isPrime), end(isPrime), true);
    isPrime[0] = isPrime[1] = false;
    for (int p = 2; p * p <= MAX; ++p)
        if (isPrime[p])
            for (int i = p * 2; i <= MAX; i += p)
                isPrime[i] = false;
}

void productOfKthPrimes(int arr[], int n, int k) {
    long long product = 1;
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        if (isPrime[arr[i]]) {
            ++cnt;
            if (cnt == k) {
                product *= arr[i];
                cnt = 0;
            }
        }
    }
    cout << "Tich = " << product << endl;
}

int main() {
    sieve();
    int arr[] = {2, 3, 11, 13, 23};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    productOfKthPrimes(arr, n, k);
    return 0;
}

Kết quả

Tich = 39

Giải thích: Mảng {2,3,11,13,23}, K=2. Số nguyên tố thứ 2 là 3, thứ 4 là 13. Tích = 3 * 13 = 39.