Как из первых N натуральных чисел составить максимальное количество пар, суммы которых являются простыми?

Для решения этой задачи нам потребуется осуществить следующие шаги:

1. Сначала создадим функцию isPrime, которая будет определять, является ли число простым. Она будет принимать целое число и возвращать булевое значение (true, если число простое, и false в противном случае).

bool isPrime(int num)
{
    if (num < 2) {
        return false;
    }
    
    for (int i = 2; i <= sqrt(num); i++) {
        if (num % i == 0) {
            return false;
        }
    }
    
    return true;
}

2. Теперь мы можем создать функцию generatePairs, которая будет генерировать максимальное количество пар из первых N натуральных чисел, суммы которых являются простыми. Функция принимает число N и возвращает вектор пар.

std::vector<std::pair<int, int>> generatePairs(int N)
{
    std::vector<std::pair<int, int>> pairs;
    
    for (int i = 1; i <= N; i++) {
        for (int j = i + 1; j <= N; j++) {
            if (isPrime(i + j)) {
                pairs.push_back(std::make_pair(i, j));
            }
        }
    }
    
    return pairs;
}

3. Наконец, мы можем использовать эти функции в нашей программе, чтобы найти максимальное количество пар для заданного значения N.

#include <iostream>
#include <vector>
#include <utility>
#include <cmath>

bool isPrime(int num)
{
    if (num < 2) {
        return false;
    }
    
    for (int i = 2; i <= sqrt(num); i++) {
        if (num % i == 0) {
            return false;
        }
    }
    
    return true;
}

std::vector<std::pair<int, int>> generatePairs(int N)
{
    std::vector<std::pair<int, int>> pairs;
    
    for (int i = 1; i <= N; i++) {
        for (int j = i + 1; j <= N; j++) {
            if (isPrime(i + j)) {
                pairs.push_back(std::make_pair(i, j));
            }
        }
    }
    
    return pairs;
}

int main()
{
    int N;
    std::cout << "Введите значение N: ";
    std::cin >> N;
    
    std::vector<std::pair<int, int>> pairs = generatePairs(N);
    
    std::cout << "Максимальное количество пар: " << pairs.size() << std::endl;
    
    std::cout << "Список пар:" << std::endl;
    for (const auto& pair : pairs) {
        std::cout << pair.first << " " << pair.second << std::endl;
    }
    
    return 0;
}

В этой программе мы сначала запрашиваем у пользователя значение N, затем вызываем функцию generatePairs, чтобы найти все пары и выводим результат в консоль.

Например, если пользователь вводит N = 5, программа выводит следующее:

Введите значение N: 5
Максимальное количество пар: 4
Список пар:
1 4
2 3
2 5
4 5

В данном примере, максимальное количество пар равно 4, а пары, суммы которых являются простыми, это: (1, 4), (2, 3), (2, 5), (4, 5).