Đếm số có thể biểu diễn dưới dạng tổng các số nguyên tố cùng chẵn lẻ trong C++

Cho mảng Arr[] chứa các số nguyên dương kích thước N. Mục tiêu là đếm số phần tử trong mảng có thể biểu diễn dưới dạng tổng các số nguyên tố cùng chẵn lẻ (parity primes), tức là có thể viết thành tổng của cùng một số nguyên tố. Ví dụ: 4 = 2+2, 6 = 3+3 hoặc 2+2+2.

Tổng của hai số nguyên tố đều lẻ hoặc đều chẵn luôn là số chẵn. Và trừ 0 và 2, tất cả các số chẵn đều có thể biểu diễn dưới dạng tổng các số nguyên tố cùng chẵn lẻ.

Hãy hiểu qua các ví dụ.

Đầu vào

Arr[] = { 2, 5, 10, 15, 20, 25 }

Đầu ra

Số thỏa mãn điều kiện: 3

Giải thích

Các số là tổng cùng số nguyên tố: Arr[0]=2: Không, Arr[1]=5: Không, Arr[2]=10: 5+5 đếm=1, Arr[3]=15: Không, Arr[4]=20: 5+5+5+5 đếm=2, Arr[5]=25: Không

Đầu vào

Arr[] = { 0, 2, 4, 11, 13 }

Đầu ra

Số thỏa mãn điều kiện: 1

Giải thích

Các số là tổng cùng số nguyên tố: Arr[0]=0: Không, Arr[1]=2: Không, Arr[2]=4: 2+2 đếm=1, Arr[3]=11: Không, Arr[4]=13: Không

Phương pháp sử dụng trong chương trình dưới đây

• Nhận mảng số nguyên dương độ dài N.
• Hàm sumofparityPrimes(int arr[], int n) nhận mảng và n, trả về số phần tử có thể biểu diễn dưới dạng tổng các số nguyên tố cùng chẵn lẻ.
• Khởi tạo biến count = 0 cho các số như vậy.
• Duyệt mảng bằng vòng lặp for.
• Với mỗi phần tử nếu nó chẵn (arr[i]%2==0).
• Kiểm tra nó khác 0 và khác 2. Nếu đúng tăng count.
• Trả về count làm kết quả sau vòng lặp.

Ví dụ

#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) { // số chẵn
            if(arr[i]!=0) {
                if(arr[i]!=2) {
                    count++;
                } // khác 0 và 2
            }
        }
    }
    return count;
}

int main() {
    int Arr[] = { 12, 5, 15, 8, 100, 40 };
    int Length = sizeof(Arr)/sizeof(Arr[0]);
    cout << endl << "Số thỏa mãn điều kiện: " << sumofparityPrimes(Arr, Length);
    return 0;
}

Đầu ra

Nếu chạy mã trên sẽ cho kết quả sau:

Số thỏa mãn điều kiện: 4