หาผลคูณของจำนวนเฉพาะทั้งหมดในอาร์เรย์ C++

ได้รับอาร์เรย์จำนวนเต็ม arr[] งานคือหาผลคูณของจำนวนเฉพาะ (Prime numbers) ทั้งหมดในอาร์เรย์

จำนวนเฉพาะ คือ จำนวนที่มากกว่า 1 และหารได้เฉพาะ 1 และตัวมันเอง (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...)

หมายเหตุ: 1 ไม่ใช่ จำนวนเฉพาะ (โค้ดต้นฉบับนับ 1 เป็นเฉพาะ → ผิด)

ตัวอย่าง

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

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

Prime ในอาร์เรย์: 11, 31, 5

Output: 1705 (11 × 31 × 5)

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

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

Prime ในอาร์เรย์: 2, 3, 5, 7 (1 ไม่ใช่เฉพาะ)

Output: 210 (2 × 3 × 5 × 7)

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

1. หาค่าสูงสุดในอาร์เรย์ max_val
2. สร้าง vector isPrime(max_val + 1, true)
3. ตั้ง isPrime[0] = isPrime[1] = false
4. วน p = 2 ถึง √max_val หาก isPrime[p] ทำเครื่องหมาย p×2, p×3, ... เป็น false
5. วนอาร์เรย์เดิม ถ้า isPrime[arr[i]] คูณสะสม

ตัวอย่างโค้ด (แก้ไข 1 ไม่ใช่ prime)

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

long long productOfPrimes(const vector<int>& arr) {
    if (arr.empty()) return 0;
    
    int maxVal = *max_element(arr.begin(), arr.end());
    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 prod = 1;
    bool found = false;
    for (int x : arr) {
        if (isPrime[x]) {
            prod *= x;
            found = true;
        }
    }
    return found ? prod : 0;  // ถ้าไม่มี prime ให้คืน 0
}

int main() {
    vector<int> arr1 = {11, 20, 31, 4, 5, 6, 70};
    cout << "Product: " << productOfPrimes(arr1) << endl;  // 1705
    
    vector<int> arr2 = {1, 2, 3, 4, 5, 6, 7};
    cout << "Product: " << productOfPrimes(arr2) << endl;  // 210
    
    vector<int> arr3 = {4, 6, 8, 9, 10};
    cout << "Product: " << productOfPrimes(arr3) << endl;  // 0 (ไม่มี prime)
    
    return 0;
}

กรณีผลคูณใหญ่เกิน 64-bit

หากผลคูณอาจล้น long long (ใหญ่กว่า ~9×10¹⁸) ควรใช้:

• __int128 (GCC/Clang extension)
• Big Integer library (Boost.Multiprecision)
• Modulo arithmetic (หากโจทย์กำหนด mod)

ความซับซ้อน

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

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

• ถือว่า 1 เป็นจำนวนเฉพาะ (isprime[1] = false แต่คำอธิบายกลับบอก 1 เป็น prime)
• Output ตัวอย่างที่ 2 บอก 210 ซึ่ง 1×2×3×5×7=210 แต่ถ้าไม่นับ 1 จะได้ 2×3×5×7=210 เหมือนกัน (บังเอิญตรง)
• ใช้ #include <bits/stdc++.h> ซึ่งไม่ใช่ standard header