หาผลคูณของจำนวนประกอบ (Composite Numbers) ทั้งหมดในอาร์เรย์ C++

งานคือหาผลคูณของจำนวนประกอบ (Composite Numbers) ทั้งหมดในอาร์เรย์

จำนวนประกอบ (Composite Number) คือ จำนวนเต็มบวกที่มากกว่า 1 และ ไม่ใช่จำนวนเฉพาะ (มีตัวหารอื่นนอกจาก 1 และตัวมันเอง)

• จำนวนประกอบแรกๆ: 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, ...
• 1 ไม่ใช่จำนวนประกอบ (คือ Unit)
• จำนวนเฉพาะไม่ใช่จำนวนประกอบ (2, 3, 5, 7, 11, ...)

ตัวอย่าง

ตัวอย่างที่ 1

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

Composite: 4, 6

Output: 24 (4 × 6)

ตัวอย่างที่ 2

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

Composite: 10, 4, 6

Output: 240 (10 × 4 × 6)

แนวทางแก้ปัญหา: Sieve of Eratosthenes

1. หาค่าสูงสุดในอาร์เรย์ maxVal
2. สร้าง isPrime[0..maxVal] ด้วย Sieve
3. จำนวนประกอบ = !isPrime[x] && x > 1
4. คูณสะสมทุกจำนวนประกอบ

ตัวอย่างโค้ด (แก้ไข Logic ให้ถูกต้อง)

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

long long productOfComposites(const vector<int>& arr) {
    if (arr.empty()) return 0;
    
    int maxVal = *max_element(arr.begin(), arr.end());
    if (maxVal < 4) return 0;  // ไม่มี composite
    
    // Sieve of Eratosthenes
    vector<bool> 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;
        }
    }
    
    long long product = 1;
    bool found = false;
    for (int x : arr) {
        if (x > 1 && !isPrime[x]) {  // Composite: >1 และไม่ใช่ prime
            product *= x;
            found = true;
        }
    }
    
    return found ? product : 0;
}

int main() {
    vector<int> arr1 = {1, 2, 4, 5, 6, 7};
    cout << "Product of composites: " << productOfComposites(arr1) << endl;  // 24
    
    vector<int> arr2 = {10, 2, 4, 5, 6, 11};
    cout << "Product of composites: " << productOfComposites(arr2) << endl;  // 240
    
    vector<int> arr3 = {2, 3, 5, 7, 11};  // samer prime
    cout << "Product of composites: " << productOfComposites(arr3) << endl;  // 0
    
    return 0;
}

ข้อผิดพลาดในโค้ดต้นฉบับ

• prime[0] = true; prime[1] = true; → ผิด! 0 และ 1 ไม่ใช่ prime ควรเป็น false
• Logic !prime[arr[i]] จะนับ 0 และ 1 เป็น composite (เพราะ prime[0]=prime[1]=true) → ผิด
• Output บอก "product of consecutive numbers" แทน "composite numbers" → คัดลอกผิด

ความซับซ้อน

• เวลา: O(maxVal log log maxVal + N)
• พื้นที่: O(maxVal)

การปรับปรุงสำหรับ N ใหญ่

หากค่าในอาร์เรย์ใหญ่มาก (10⁹+) ใช้ Miller-Rabin Primality Test แทน Sieve:

bool isPrime(long long n) {
    if (n < 2) return false;
    for (long long p : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
        if (n % p == 0) return n == p;
    }
    // Miller-Rabin deterministic for 64-bit
    long long d = n - 1, s = 0;
    while ((d & 1) == 0) { d >>= 1; s++; }
    for (long long a : {2, 325, 9375, 28178, 450775, 9780504, 1795265022}) {
        if (a % n == 0) continue;
        long long x = 1, p = d;
        // modular exponentiation a^d mod n
        long long base = a % n;
        while (p) {
            if (p & 1) x = (__int128)x * base % n;
            base = (__int128)base * base % n;
            p >>= 1;
        }
        if (x == 1 || x == n - 1) continue;
        bool composite = true;
        for (int r = 1; r < s; r++) {
            x = (__int128)x * x % n;
            if (x == n - 1) { composite = false; break; }
        }
        if (composite) return false;
    }
    return true;
}