Đếm số cặp có tổng là số nguyên tố và nhỏ hơn n trong C++

Cho một số nguyên dương n. Mục tiêu là tìm số lượng cặp (i, j) sao cho tổng (i + j) là số nguyên tố và nhỏ hơn n. Điều kiện: i != j và i, j >= 1. Nếu n = 4, chỉ có 1 cặp (1, 2) vì 1+2=3 là số nguyên tố và 3 < 4.

Ví dụ

Đầu vào − n = 7

Đầu ra − 3

Giải thích − Các cặp: (1,2), (1,4), (2,3). Tổng: 3, 5, 5 đều là số nguyên tố < 7.

Đầu vào − n = 10

Đầu ra − 6

Giải thích − Các cặp: (1,2), (1,4), (2,3), (1,6), (2,5), (3,4). Tổng: 3, 5, 5, 7, 7, 7 đều là số nguyên tố < 10.

Phương pháp giải

Sử dụng sàng Sundaram để tìm tất cả số nguyên tố nhỏ hơn n trong hàm check_prime(bool check[], int temp).

Với mỗi số lẻ temp, số cặp khác nhau có tổng bằng temp là temp/2. Trừ số 2, mọi số nguyên tố đều lẻ. Với mỗi số nguyên tố temp < n, cộng temp/2 vào kết quả.

• Nhận biến n.
• Hàm prime_pair(int n) trả về số cặp thỏa mãn.
• Khởi tạo count = 0.
• Sàng Sundaram sinh số nguyên tố < 2*n+2 cho đầu vào n. Giảm n xuống một nửa lưu vào temp_2.
• Tạo mảng Check[] độ dài temp_2 đánh dấu các số dạng (i+j+2*i*j) là true. Khởi tạo tất cả false.
• Gọi check_prime(check, temp_2) để đánh dấu.
• Duyệt Check[] từ i=0 đến temp_2-1:
  • Nếu check[i] == false, số nguyên tố temp = 2*i + 1.
  • Số cặp có tổng temp là temp/2.
  • Cộng vào count.
• Trả về count.

Ví dụ code

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

void check_prime(bool check[], int temp) {
    for (int i = 1; i <= temp; i++) {
        for (int j = i; (i + j + 2*i*j) <= temp; j++) {
            check[i + j + 2*i*j] = true;
        }
    }
}

int prime_pair(int n) {
    int count = 0;
    int temp;
    int temp_2 = (n - 2) / 2;
    bool check[temp_2 + 1];
    memset(check, false, sizeof(check));
    check_prime(check, temp_2);
    for (int i = 1; i <= temp_2; i++) {
        if (check[i] == false) {
            temp = 2*i + 1;
            count += (temp / 2);
        }
    }
    return count;
}

int main() {
    int n = 10;
    cout << "Count of pairs with sum as a prime number and less than n are: " << prime_pair(n);
    return 0;
}

Đầu ra

Count of pairs with sum as a prime number and less than n are: 6