XOR ของจำนวนเฉพาะทั้งหมดในอาร์เรย์ (C++)

โจทย์

ได้รับอาร์เรย์ขนาด n ต้องการหา XOR ของจำนวนเฉพาะ (prime numbers) ทั้งหมดในอาร์เรย์

ตัวอย่าง

Input: {2, 6, 8, 9, 11}
Output: 2 ^ 11 = 9 (เพราะ 2 และ 11 เป็นจำนวนเฉพาะ)

วิธีแก้ปัญหา

ใช้ Sieve of Eratosthenes (โครงรังกรองของเอราโธสเธนีส) หาจำนวนเฉพาะทั้งหมดจนถึงค่าสูงสุดในอาร์เรย์
วนลูปตรวจสอบแต่ละองค์ประกอบในอาร์เรย์ ว่ามีอยู่ในรายการจำนวนเฉพาะหรือไม่
ถ้าเป็นจำนวนเฉพาะ ให้ทำ XOR สะสมเข้าไปในผลลัพธ์

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

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

const int MAX_N = 100005;
bool prime[MAX_N];

void SieveOfEratosthenes(int n) {
    memset(prime, true, sizeof(prime));
    prime[0] = prime[1] = false;
    for (int p = 2; p * p <= n; p++) {
        if (prime[p]) {
            for (int i = p * 2; i <= n; i += p) {
                prime[i] = false;
            }
        }
    }
}

int findXorOfPrimes(int arr[], int n) {
    SieveOfEratosthenes(MAX_N - 1);
    int result = 0;
    for (int i = 0; i < n; i++) {
        if (prime[arr[i]]) {
            result ^= arr[i];
        }
    }
    return result;
}

int main() {
    int arr[] = {4, 3, 2, 6, 100, 17};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The xor of all prime number of the array is: " << findXorOfPrimes(arr, n);
    return 0;
}

ผลลัพธ์

The xor of all prime number of the array is: 16

คำอธิบาย: จำนวนเฉพาะในอาร์เรย์คือ 3, 2, 17 → 3 ^ 2 ^ 17 = 16

การปรับปรุงประสิทธิภาพ

คำนวณ Sieve เพียงครั้งเดียว (static/global) หากเรียกฟังก์ชันหลายครั้ง
ใช้ vector<bool> แทน array เพื่อประหยัดหน่วยความจำ
สำหรับค่าสูงมาก (> 10⁷) ควรใช้ segmented sieve

Complexity

Time: O(MAX_N log log MAX_N + n) - 主導โดย Sieve
Space: O(MAX_N) - สำหรับ boolean array

สรุป

การรวม Sieve of Eratosthenes กับ XOR operation ให้วิธีแก้ปัญหาที่มีประสิทธิภาพสำหรับการหา XOR ของจำนวนเฉพาะในอาร์เรย์ เหมาะสำหรับค่าที่ไม่ใหญ่เกินไป (≤ 10⁶)