นับและหาผลรวมของจำนวนประกอบในอาร์เรย์ใน C++

เราได้รับอาร์เรย์ของจำนวนเต็มบวก งานคือการนับและหาผลรวมของจำนวนประกอบ (composite numbers) ในอาร์เรย์

จำนวนประกอบคืออะไร?

จำนวนเต็มที่ไม่ใช่จำนวนเฉพาะและไม่ใช่ 1 (เพราะ 1 ไม่ใช่เฉพาะและไม่ใช่ประกอบ) เช่น 4, 6, 8, 9, 10, 12, 14, 15...

ตัวอย่าง

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

คำอธิบาย − จำนวนประกอบ: 4,6,8,9,10 รวม 5 ตัว ผลรวม = 37

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

คำอธิบาย − มีแค่ 4 เป็นจำนวนประกอบ

แนวทางการแก้ปัญหา

• หาค่าสูงสุดในอาร์เรย์
• ใช้ Sieve of Eratosthenes หาจำนวนเฉพาะถึงค่าสูงสุด
• วนลูปอาร์เรย์ ถ้าไม่ใช่เฉพาะและไม่ใช่ 1 ให้เป็นจำนวนประกอบ นับและบวกผลรวม

ตัวอย่างโค้ด C++

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

int compositeCount(int ar[], int n, int* sum) {
    int maxVal = *max_element(ar, ar + n);
    vector isPrime(maxVal + 1, true);
    isPrime[0] = isPrime[1] = false;
    
    for (int p = 2; p * p <= maxVal; p++) {
        if (isPrime[p]) {
            for (int i = p * 2; i <= maxVal; i += p)
                isPrime[i] = false;
        }
    }
    
    int count = 0;
    *sum = 0;
    for (int i = 0; i < n; i++) {
        if (!isPrime[ar[i]] && ar[i] != 1) {
            count++;
            *sum += ar[i];
        }
    }
    return count;
}

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

ผลลัพธ์

Count = 1 Sum = 4