Гипотеза Гольдбаха
(Время: 1 сек. Память: 16 Мб Сложность: 30%)
Для поиска такого разложения числа n достаточно перебрать всевозможные комбинации таких пар натуральных чисел a и b таких, что a+b=n и a<=b, и проверить их на простоту. Момент проверки числа на простоту в виде реализации функции IsPrime уже рассматривался здесь. Поэтому несложно оформить решение данной задачи в виде следующего алгоритма:
bool IsPrime(int n){
int i;
for i=2..sqrt(n)
if(n mod i = 0) return false;
return true;
}
read(n);
for i=2 .. n div 2
if(IsPrime(i) and IsPrime(n-i)){
write(i,' ',n-i);
break;
}
|