Упражнения на C ++: принять целое число (n) от пользователя и вывести число комбинаций, которые выражают n как сумму двух простых чисел

C ++ Basic: упражнение 76 с решением

Четное число 4 или более может быть представлено суммой двух простых чисел. Это называется ожиданием Гольдбаха, и подтверждается, что оно вычисляется с помощью компьютерного расчета до значительно большего числа. Например, 10 может быть выражено как сумма двух простых чисел 7 + 3, 5 + 5.
Напишите программу на C ++, которая принимает целое число (n) от пользователя и выводит количество комбинаций, которые выражают n как сумму двух простых чисел.
Примечание: n должно быть больше или равно 4 и меньше или равно 50 000.

Пример решения :

Код C ++:

#include <iostream>
using namespace std;
 
int search(const int array[], int high, int key)
{
    int low_num = 0;
    int mid_num;
    int n=-1;
    while(low_num<=high){
        mid_num = (low_num + high)/2;
        if( array[mid_num] == key ){
            n = mid_num;
            break;
        }else if ( array[mid_num] < key){
            low_num = mid_num + 1;
        }else{
            high = mid_num -1;
        }
    }
    return(n);
}
 
int main(void){
    int prime_num[5136];
    prime_num[1] = 2;
    prime_num[2] = 3;
    int ptr=3;
    for(int num=5; num<=50000; num++){
        bool f = false;
        for(int i=1; i<ptr; i++){
            if(prime_num[i]*prime_num[i] > num){
                break;
            }
            if(num%prime_num[i]==0) {
                f = true;
                break;
            }
        }
        if(!f) {
            prime_num[ptr++] = num;
        }
    }
    prime_num[ptr] = 50001;
    int n;
    while(cin >> n){
        if(!n) break;
        int count = 0;
        if(n%2==0){
            for(int i=1; prime_num[i] <= n/2; i++){
                    if(search(prime_num,ptr,n-prime_num[i])!=-1) count++;
            }
        }else{
            if(search(prime_num,ptr,n-2)!=-1) count++;
        }
        cout << "Input number: " << n;
        cout << "\nNumber of combinations: " << count << endl;
    }
    return 0;
}

Пример вывода:

 Введите номер: 7
Количество комбинаций: 1
Введите номер: 85
Количество комбинаций: 1
Входной номер: 900
Количество комбинаций: 48
Введите номер: 1505
Количество комбинаций: 0

Блок - схема:

Редактор кода C ++:

Внесите свой код и комментарии через Disqus.

Предыдущий: Напишите программу на C ++ для вычисления суммы указанного числа простых чисел.
Далее: Напишите программу на C ++, чтобы проверить, являются ли две прямые линии AB и CD ортогональными или нет.