Практика программирования (Бейсик, Си, Паскаль)


Задачи,советы и ответы - часть 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.




- Начало -  - Назад -  - Вперед -