автор: Горский С.С.

Простые числа в Лого

Мне бы хотелось рассмотреть решение задач основной части Дистанционной обучающей олимпиады, частью которой является наш проект. Решения, реализованные на Лого. Вообще, в период подготовки Лого-секции А.Г Юдиной высказывалась мысль, что, проводя отдельную Лого-олимпиаду, мы как бы подразумеваем, что задачи основной части невозможно решить на Лого. И тем самым существенно принижаем возможности и мнение о Лого. Частично разделяя это утверждение, мне показалось интересным рассмотреть задачи основной части на Лого. Что касается нашей Лого-олимпиады, мне кажется, что она вполне естественна, т.к. все же возрастной уровень изучающих лого в целом не очень высок. И наша олимпиада, к тому же двух уровневая, учитывает эти реалии. Тем более, что в итоге, среди команд основной части ни одна не писала на Лого, хотя язык это в некоторых школах-участниках изучается, и строго язык программирования олимпиады не регламентировался.
На сегодня предлагаю вашему вниманию наиболее простую задачу - наиболее рациональный способ поиска большого количества простых чисел (речь идет о числа порядка 100000000). Я уже реализую идеи, примененные как нашей командой, выступающей в основной части (на Паскале и Си), так и других команд, прозвучавших в дальнейшем обсуждении.(Правда, и числа до 100000000 я не рассматривал.)

Идеи таковы.

Все найденные числа заносятся в список, и при проверке на "простоту" числа делители берутся только из списка. Это позволяет не проверять делимость на составные числа.

Второе. Простые числа, начиная с 5, должны лежать на множестве чисел вида 6*к-1 или 6*к+1. Поэтому в качестве "кандидатов" на простые числа выбираем только их.

Не берусь утверждать, что это лучший возможные алгоритм. Хотелось бы отметить, что борясь за структурность и при отсутствии цикла While do или Repeat until, имеющихся в Паскале, я рассмотрел два варианта алгоритма проверки на делимость конкретного числа. Вариант ДЕЛИМОСТЬ2 в итоге был отметен, хотя он, возможно, более красив - он использует рекурсию, и помог добраться до чисел в пределах 14000. Второй, и окончательный вариант, использует ПОВТОРИ и принудительный выход.

Если кто-либо предложит еще вариант, будет здорово.

это делимость
повтори 3 * :к [

пусть "д :д + 1
пусть "о остаток :ч элемент :д :прост
если :о = 0 [пусть "рез 0 ]
если не (и :рез = 1 (элемент :д :прост) < :ч / 2) [стоп]

]
конец

 это простое
пусть "к 1
пусть "прост (список 2 3)
покажи "поехали
повтори 10000 [

пусть "д 0
пусть "ч 6 * :к - 1
пусть "рез 1
делимость
если :рез = 1[пусть "прост вксп :ч :прост ]
пусть "д 0
пусть "ч 6 * :к + 1
пусть "рез 1
делимость
если :рез = 1[пусть "прост вксп :ч :прост ]
пусть "к :к + 1]

покажи :прост
конец
это делимость2
пусть "д :д + 1
пусть "о остаток :ч элемент :д :прост
если :о = 0 [пусть "рез 0 ]
если (и :рез = 1 (элемент :д :прост) < :ч / 2) [делимость]
конец

P.S. Буду очень рад, если найдутся еще желающие прорешать задачи основной части на Лого. Если для этого необходимо переслать задачи остальной части, пришлите запрос.

С уважением, Горский Сергей Сергеевич.