Đếm và tổng các số hợp thành trong mảng C++

Cho mảng số nguyên dương, nhiệm vụ là đếm và tính tổng các số hợp thành (composite numbers) trong mảng.

Số hợp thành là gì?

Số nguyên dương > 1 không phải số nguyên tố. Số 1 không phải nguyên tố cũng không phải hợp thành. Các số hợp thành ≤ 100: 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50, 51, 52, 54, 55, 56, 57, 58, 60, 62, 63, 64, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80, 81, 82, 84, 85, 86, 87, 88, 90, 91, 92, 93, 94, 95, 96, 98, 99, 100.

Ví dụ

Input - array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} Output - Count: 5, Sum: 37

Giải thích - Số hợp thành: 4, 6, 8, 9, 10. Tổng = 37.

Input - array[] = {1, 2, 3, 4, 5} Output - Count: 1, Sum: 4

Phương pháp tiếp cận (Sieve)

• Tìm max trong mảng
• Dùng Sieve of Eratosthenes tìm số nguyên tố đến max
• Duyệt mảng: nếu không phải nguyên tố và > 1 → là hợp thành, count++ và cộng sum

Ví dụ code C++

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

int compcount(int ar[], int num, int* sum) {
    int max_val = *max_element(ar, ar + num);
    vector<bool> pr(max_val + 1, true);
    pr[0] = pr[1] = true; // 0,1 không phải nguyên tố

    for (int p = 2; p * p <= max_val; p++) {
        if (pr[p]) {
            for (int i = p * 2; i <= max_val; i += p)
                pr[i] = false;
        }
    }

    int ans = 0;
    for (int i = 0; i < num; i++) {
        if (!pr[ar[i]]) {
            ans++;
            *sum += ar[i];
        }
    }
    return ans;
}

int main() {
    int ar[] = {1, 2, 3, 4, 5};
    int num = sizeof(ar) / sizeof(ar[0]);
    int sum = 0;
    cout << "Count of Composite Numbers = " << compcount(ar, num, &sum);
    cout << "\nSum of Composite Numbers = " << sum;
    return 0;
}

Kết quả

Count of Composite Numbers = 1 Sum of Composite Numbers = 4