Практика программирования (Бейсик, Си, Паскаль)
Задачи,советы и ответы - часть 39
writeln;
write(' Среди первых ',maxk+l, ' нечетных чисел ');
writeln(' найдено ',n,' простых');
readln;
end.
Программа 2_22a.pas
program sieve; uses Crt; const
maxN=255; (не более 255} var
primes: set of 2..maxN;
i,j:integer;
begin clrscr;
primes:=[2..maxN]; { первоначальная роспись папируса }
for i:=2 to maxN do
if i in primes then { если i принадлежит множеству }
begin
write (i:5); { вывод очередного простого числа }
for j : =1 to maxN div i do
primes:=primes-[i*j]; { удаление чисел, кратных i}
end;
readln;
end.
Задание 2.23. Разложение четного числа на сумму простых чисел
В 1742 г. Христиан Гольдбах высказал предположение, что любое четное число можно представить в виде суммы двух простых чисел, а любое нечетное — в виде суммы трех простых чисел. На самом деле, вторая часть утверждения Гольдбаха является следствием первой. Если из нечетного числа вычесть подходящее простое, то остаток будет четным, и как только его удастся разложить на сумму двух простых, первоначальное нечетное число будет равно сумме трех простых чисел. Несмотря на кажущуюся простоту проблемы Гольдбаха, до сих пор ее справедливость ни доказана, ни опровергнута. Более того, в начале 2000 г. английский книгоиздатель Фейбер предложил награду в размере 1 миллиона долларов тому, кто сумеет доказать или опровергнуть предположение Гольдбаха.
Предлагается провести численный эксперимент, который, к сожалению, не претендует на получение объявленной награды. Составим программу, которая находит все возможные разложения числа п на сумму двух простых чисел.
Совет 1 (общий)
Самый простой вариант поиска нужного разложения заключается в переборе сумм вида k + (n - k). Если оба слагаемых оказались простыми, то искомое разложение найдено. Анализ слагаемых можно организовать с помощью функции prime, построенной в одном из предыдущих заданий. Естественно, что начать перебор можно с k = 2, а затем в качестве первого слагаемого пробовать все нечетные числа, не превосходящие п/2.