ภาพรวมปัญหา
ให้อาร์เรย์ Arr[] ของจำนวนเต็มบวกขนาด N ต้องการนับจำนวนสมาชิกที่สามารถเขียนเป็นผลรวมของจำนวนเฉพาะที่มีค่าเท่ากันได้ เช่น 4 = 2+2, 6 = 3+3 หรือ 2+2+2
ข้อสังเกตทางคณิตศาสตร์
- ผลรวมของจำนวนเฉพาะคู่ (2) หรือคี่ (3,5,7...) จะได้เลขคู่เสมอ
- ยกเว้น 0 และ 2 แล้ว เลขคู่ทุกตัวสามารถเขียนเป็นผลรวมของจำนวนเฉพาะค่าเท่ากันได้
- เหตุผล: เลขคู่ ≥ 4 สามารถเขียนเป็น 2+2+...+2 ได้เสมอ
ตัวอย่าง
Input: Arr[] = {2, 5, 10, 15, 20, 25}
Output: 3
คำอธิบาย: 10=5+5, 20=5+5+5+5+5 (นับ 10, 20 และอีกตัวหนึ่ง)
Input: Arr[] = {0, 2, 4, 11, 13}
Output: 1
คำอธิบาย: 4 = 2+2 เท่านั้น
แนวทางแก้ปัญหา
- ฟังก์ชัน
sumofparityPrimes(int arr[], int n) - ตัวแปร
countเริ่มต้นที่ 0 - วนลูปตรวจสอบแต่ละสมาชิกในอาร์เรย์
- ถ้าเป็นเลขคู่ (arr[i] % 2 == 0) และ ไม่ใช่ 0 และ ไม่ใช่ 2 ให้เพิ่ม count
- คืนค่า count
โค้ดตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int sumofparityPrimes(int arr[], int n) {
int count = 0;
for (int i = 0; i < n; i++) {
if (arr[i] % 2 == 0 && arr[i] != 0 && arr[i] != 2) {
count++;
}
}
return count;
}
int main() {
int Arr[] = {12, 5, 15, 8, 100, 40};
int Length = sizeof(Arr) / sizeof(Arr[0]);
cout << "Number which satisfy condition: " << sumofparityPrimes(Arr, Length);
return 0;
}
ผลลัพธ์
Number which satisfy condition: 4
ความซับซ้อน
- เวลา: O(N) - ตรวจสอบแต่ละสมาชิกเพียงครั้งเดียว
- พื้นที่: O(1)
หมายเหตุ
โจทย์ระบุ "same parity primes" หมายถึงจำนวนเฉพาะที่มีความคี่/คู่เหมือนกัน (2 กับ 2, หรือ 3 กับ 3, 5 กับ 5) ซึ่งจนจบลงที่เงื่อนไข "เลขคู่ที่ไม่ใช่ 0 และ 2"
