Đếm tổng khác nhau từ cặp số nguyên tố hai mảng trong C++

Giới thiệu

Cho hai mảng, tìm số lượng tổng khác nhau của các cặp (x từ arr1, y từ arr2) với x, y đều là số nguyên tố.

Ví dụ

• Arr1 = [1,2,3], Arr2 = [2,3,4] → Số nguyên tố: (2,3) và (2,3) → Cặp: (2,2)=4, (2,3)=5, (3,2)=5, (3,3)=6 → Tổng khác nhau: {4,5,6} → 3
• Arr1 = [1,4,6], Arr2 = [2,3,5] → Arr1 không có số nguyên tố → 0

Ý tưởng giải thuật

1. Hàm isPrime(n) kiểm tra số nguyên tố.
2. Duyệt tất cả cặp (i,j), nếu cả hai đều nguyên tố thì thêm tổng vào unordered_set.
3. Trả về kích thước set.

Ví dụ triển khai (C++)

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

bool isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i * 1LL * i <= n; i++)
        if (n % i == 0) return false;
    return true;
}

int countDistinctPrimeSums(vector<int> a, vector<int> b) {
    unordered_set<int> sums;
    for (int x : a)
        if (isPrime(x))
            for (int y : b)
                if (isPrime(y))
                    sums.insert(x + y);
    return sums.size();
}

int main() {
    vector<int> a = {2, 3, 5};
    vector<int> b = {2, 2, 4, 7};
    cout << "So tong khac nhau: " << countDistinctPrimeSums(a, b); // 5 (4,5,7,8,10)
    return 0;
}

Đầu vào

Arr1=[2,3,5], Arr2=[2,2,4,7]

Đầu ra

5