Tích các số hợp số (Composite) trong mảng trong C++

Cho mảng arr[]. Nhiệm vụ: tính tích các số hợp số (composite numbers) trong mảng.

Số hợp số: số nguyên > 1 không phải số nguyên tố (có ước ngoài 1 và chính nó). Ví dụ: 4, 6, 8, 9, 10...

Lưu ý: 1 không phải số nguyên tố cũng không phải số hợp số.

Ví dụ 1

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

Output – 24

Giải thích: Số hợp số: 4, 6. Tích = 24.

Ví dụ 2

Input – arr[] = {10, 2, 4, 5, 6, 11}

Output – 240

Giải thích: Số hợp số: 10, 4, 6. Tích = 240.

Thuật toán (Sieve)

1. Tìm max_val trong mảng.
2. Sàng Eratosthenes tìm số nguyên tố đến max_val.
3. Số > 1 và không phải nguyên tố → hợp số.
4. Nhân các số hợp số.

Ví dụ code

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

long long productOfComposites(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++) {
        int x = arr[i];
        if (x > 1 && !isPrime[x]) { // >1 và không phải nguyên tố = hợp số
            prod *= x;
            found = true;
        }
    }
    return found ? prod : 0;
}

int main() {
    int arr[] = {2, 4, 6, 8, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Product of composites: " << productOfComposites(arr, n) << endl;
    return 0;
}

Kết quả

Product of composites: 1920

Giải thích: Tất cả 4,6,8,10 là hợp số. 2 là nguyên tố. Tích = 4×6×8×10 = 1920.