Решение задачи №323 «Гипотеза Гольдбаха
» с ACMP
Условие задачи
Известно, что любое чётное число, большее 2, представимо в виде суммы 2 простых чисел, причём таких разложений может быть несколько. Впервые гипотезу о существовании данного разложения сформулировал математик Х. Гольдбах.
Требуется написать программу, производящую согласно утверждению Гольдбаха, разложение заданного чётного числа. Из всех пар простых чисел, сумма которых равна заданному числу, требуется найти пару, содержащую наименьшее простое число.
Входные данные
Входной файл INPUT.TXT содержит чётное число N (4 ≤ N ≤ 998).
Выходные данные
В выходной файл OUTPUT.TXT необходимо вывести два простых числа, сумма которых равна числу N. Первым выводится наименьшее число.
Решение на C++
#include<iostream>
using namespace std;
main (){
int i,j,m;
cin>>m; bool a[m];
for(i=2;i<m;++i)a[i]=true;
for(i=2;i*i<m;++i)
if(a[i])for(j=i+i;j<m;j+=i)a[j]=false; i=2;
while(!(a[i]&&a[m-i]))i++;
cout<<i<<' '<<m-i;
}
Условия задач взяты с сайта acmp.ru