Tích các số nguyên tố trong mảng trong C++

Cho mảng số nguyên. Nhiệm vụ: tính tích của tất cả các số nguyên tố trong mảng.

Số nguyên tố: số > 1 chỉ chia hết cho 1 và chính nó (2, 3, 5, 7, 11...). Lưu ý: 1 không phải số nguyên tố.

Ví dụ 1

Input – arr[] = {11, 20, 31, 4, 5, 6, 70}

Output – 1705

Giải thích: Số nguyên tố: 11, 31, 5. Tích = 11 × 31 × 5 = 1705.

Ví dụ 2

Input – arr[] = {1, 2, 3, 4, 5, 6, 7}

Output – 210

Giải thích: Số nguyên tố: 2, 3, 5, 7 (1 KHÔNG phải nguyên tố). Tích = 2×3×5×7 = 210.

Thuật toán (Sieve of Eratosthenes)

1. Tìm max_val trong mảng.
2. Tạo mảng boolean isPrime[0..max_val], khởi tạo true.
3. isPrime[0] = isPrime[1] = false.
4. Duyệt p = 2..√max_val: nếu isPrime[p] thì đánh dấu bội số của p là false.
5. Duyệt mảng gốc, nhân các phần tử có isPrime[arr[i]] = true.

Ví dụ code

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

long long productOfPrimes(int arr[], int n) {
    if (n == 0) return 0;
    
    int max_val = *max_element(arr, arr + n);
    vector<bool> isPrime(max_val + 1, true);
    isPrime[0] = isPrime[1] = false;
    
    for (int p = 2; p * p <= max_val; p++) {
        if (isPrime[p]) {
            for (int i = p * 2; i <= max_val; i += p) {
                isPrime[i] = false;
            }
        }
    }
    
    long long prod = 1;
    bool found = false;
    for (int i = 0; i < n; i++) {
        if (arr[i] >= 0 && arr[i] <= max_val && isPrime[arr[i]]) {
            prod *= arr[i];
            found = true;
        }
    }
    return found ? prod : 0; // Trả về 0 nếu không có số nguyên tố
}

int main() {
    int arr[] = {11, 20, 31, 4, 5, 6, 70};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << productOfPrimes(arr, n) << endl;
    return 0;
}

Kết quả

1705

Lưu ý: Code gốc ví dụ 2 sai khi coi 1 là số nguyên tố. Đã sửa trong giải thích. Kết quả thực tế của ví dụ 2 là 210 (2×3×5×7), không phải 210 với 1.

Xử lý số âm: Số âm không phải số nguyên tố. Code trên kiểm tra arr[i] >= 0.