Кузнецова И.Н. По поводу программирования любых задач на LOGO.

Уже давно (в 1996 году) Горлицкая С.И. и Кузнецова И.Н. подготовили задачник по LOGO "Играем со словами и списками". К сожалению этот задачник не нашел своего издателя.
Предлагаю (на правах соавтора) вам главу из него. В нее входят вопросы делимости и, в том числе - поиск простых чисел.

4. Делимость натуральных чисел
Программы этого раздела предназначены для исследований вопросов делимости чисел. Определения и правила, даваемые в 6-м классе, могут быть объяснены компьютеру, после чего компьютер будет в состоянии находить делители, НОД, НОК и сообщать другие подробности из жизни натуральных чисел.

4.1 Вспомогательные программы
Прежде чем приступить к теории, потренируемся на вспомогательных программах, которые потом нам пригодятся.
4.1.1. Формирование булевского результата
Следующие две функции предложены скорее для красоты, чем по необходимости. В системе LOGOWRITER значения булевских переменных задаются константами "истина и "ложь. Это не совсем удобно при использовании английской нотации языка. Предлагаемые функции позволят использовать общепринятые в языках программирования слова - true и false.

to true
op 1 = 1
end

to false
op 1 = 2
end

4.1.2. Проверка входного списка
Наши программы должны работать со списком целых чисел. Для упрощения алгоритма и повышения его надежности будем проверять, действительно ли входной список (переменная "l) является одномерным и состоит только из целых чисел.

to numlist :l
if empty? :l [op 0]
name 1 "i
repeat count :l[name item :i :l "t
ifelse number? :t
[ifelse equal? int :t :t
[ name :i + 1 "i]
[ op false]]
[op false]]
op true
end

4.1.3. Подсчет суммы элементов

Функция sum возвращает сумму элементов своего числового списочного аргумента, для нечислового - возвращает 0.
to sum :l
if not numlist :l [op 0]
name 0 "s
name 1 "i
repeat count :l[name :s + item :i :l "s
name :i + 1 "i]
op :s
end

4.2. Делители
Здесь рассматриваются программы, позволяющие найти делители натурального числа, проверить число на четность, находить простые числа, определять Наибольший Общий Делитель (НОД).

4.2.1. Делители натурального числа
Функция delivers сообщает список, состоящий из делителей заданного числа :x. Если параметр "x имеет нечисловое значение, функция возвращает пустой список.
Делителем является тозначение :d, для которого:
remainder :x :d = 0
Достаточно найти все делители, меньшие :x / 2

to delivers :x
name [1] "dlist
if not number? :x [ op []]
name int :x / 2 "b
name 2 "d
repeat :b[if equal? remainder :x :d 0 [name lput :d :dlist "dlist]
name :d + 1 "d]
op lput :x :dlist
end

Функция delivers1 возвращает тот же результат, но алгоритм нахождения делителей более экономный - определяются сначала делители, не превышающие корень квадратный из х, все прочие делители получатся делением числа х на найденные ранее.

to delivers1 :x
name [1] "dlist
if not number? :x [ op []]
name sqrt :x "b
name 2 "d
repeat :b[if equal? remainder :x :d 0 [name lput :d :dlist "dlist]
name :d + 1 "d]
name count :dlist "c
name :c "i
if equal? :b * :b :x [name bl :dlist "dlist
name :c - 1 "c]
repeat :c[name lput ( :x / item :i :dlist) :dlist "dlist
name :i - 1 "i]
op :dlist
end

4.2.3. Количество делителей

Функция qdel возвращает количество делителей своего числового аргумента, в случае нечислового аргумента - возвращает нулевой результат.

to qdel :x
if not number? :x [ op 0]
op count delivers1 :x
end

4.2.4. Сумма делителей
Функция sumdel возвращает сумму всех делителей числа. задаваемого параметром "x. Если :x имеет нечисловое значение, функция принимает значение 0.

to sumdel :x
op sum delivers1 :x
end

4.2.5. Четное число
Функция odd принимает значение true, если число :x - четное, и false в противном случае.

to odd :x
if equal? 0 remainder :x 2 [op false]
op true
end

4.2.6. Простые числа

Проблема поиска простых чисел занимает умы математиков до сих пор. Доказать, что число А является простым, можно, например, убедившись в отсутствии у него любых делителей, кроме 1 и самого числа А. Процесс этот очень трудоемкий. Естественно поручить эту работу компьютеру.
Предикат (датчик, функция) simpl проверяет, является ли заданное число :x ли простым. Для заданного числа тестируются все числа от 2 до :x / 2.

to simpl :x
if not number? :x [op false]
if equal? 0 :x [op true]
if or equal? 2 :x equal? 3 :x [op true]
if not odd :x [op false]
name 3 "d
repeat :x / 2 [if equal? 0 remainder :x :d [op false]
name :d + 1 "d]
op true
end

Функция nextsimpl возвращающает следующее за аргументом простое число.
К натуральному числу, следующему за данным, применяем ту же функцию next_simpl, т.е. используем рекурсивный вызов функции, но уже с другими параметрами. Если очередное число окажется простым (функция simpl возвратит значение "истина), программа закончит работу и сообщит результат.

to nextsimpl "x
ifelse simpl :x + 1 [op :x + 1][op nextsimpl :x + 1]
end

Возможно очередное простое число окажется за пределами допустимых в среде LW. Тогда функция закончится аварийно. Можно, однако, предупредить эту ситуацию, включив проверку:
:x = 999999999999

to nextsimpl "x
if :x > 999999999998 [0]
ifelse simpl :x + 1 [op :x + 1][op nextsimpl :x + 1]
end

Предлагаемые программы работают с числами в пределах от 0 до 9999 9999 9999. Может быть вам удастся поднять верхнюю границу, воспользовавшись идеями раздела 2.

4.2.7. Простые сомножители

Разложить на простые сомножители натуральное число - значит получить список ВСЕХ сомножителей, каждый из которых является простым числом. Вспомогательная функция md определяет число входимостей делителя d в число простых сомножителей числа x и возвращает результат в виде двухэлементного списка:
- первый элемент представляет собой список с числом элементов, равным максимально возможной степени числа d, допустимой при делении x на d,(т. е. сколько раз х на d делится);
- второй элемент есть остаток от деления x на максимально возможную степень числа d, допустимую в качестве делителя.

to md :x :d
name [] "ld
name [] "l
repeat 9999 [ifelse equal? 0 remainder :x :d
[name lput :d :ld "ld name :x / :d "x]
[name list :ld :x "l op :l]]
op list :ld "
end

Функция muldel выполняет разложение своего аргумента на простые сомножители и сообщает результат - двухэлементный список :
- первый элемент - искомое разложение аргумента;
- второй - число "1", выполняющее роль индикатора завершения процесса разложения на простые сомножители.
Сначала программа явно проверяет делимость заданного числа на простые числа от 2 до 5. При этом функция md формирует список входимости делителя в заданное число. Простые числа, большие 5 находятся с помощью функции next_simpl.
В программе используется трассировка выполнения - в командный центр выводятся символы ! в количестве, равном простому числу, которое тестируется в качестве делителя. Это делается командой вида:

show "!!!

В этом случае тестируется число 3.

to muldel :x
if not number? :x [op [] ]
if equal? 1 :x [op [[1] 1]]
if equal? 2 :x [op [[2] 1]]
if equal? 3 :x [op [[3] 1]]
name md :x 2 "l2
(show "! :l2)
if equal? 1 last :l2 [op :l2]
name md last :l2 3 "l3
( show "!! :l3)
if and equal? 1 last :l3 empty? first :l2 [op :l3]
ifelse not empty? first :l3 [ name lput first first :l3 first :l2 "lc
name list :lc last :l3 "ldel
(show "!!! :l3 :ldel)]
[ name :l2 "ldel (show "!!!! :ldel)]
if not equal? 1 last :ldel
[name 5 "d (show "!!!!! )
repeat 20000 [name md last :ldel :d "lt
(show "!!!!! :d :lt)
if not empty? first :lt
[name lput first first :lt first :ldel "lc
name list :lc last :lt "ldel
if equal? 1 last :ldel [op :ldel]]
name next_simpl :d "d] ]
(show "!!!!!!! :ldel)
op :ldel
end

4.2.8. Простые делители

Функция simpl_del формирует и сообщает список простых делителй для заданного числа "x. Для нечислового аргумента возвращается пустой список. Эта программа использует функции delivers и simpl.

to simpl_del :n
if not number? :x [op []]
name delivers :n "h
name [] "tlist name 1 "i
repeat count :h[name item :i :h "t show :i
if simpl :t [ name lput :t :tlist "tlist]
name :i + 1 "i]
op :tlist
end

4.3.Наибольший Общий Делитель (НОД)

Алгоритм определения наибольшего общего делителя был изложен Евклидом в его знаменитых " Началах" (330-320 гг. до н.э.). Запись его на ЛОГО очень изящна:

to nod "x "y
ifelse :x = 0 [op :y]
[op nod remainder :y :x :x]
end

Здесь "x и "y обозначают числа, для которых надо найти НОД.
Есть только одно замечание: хорошо бы проверить, являются ли целыми числа :x и :y.
Интересно найти НОД для более чем двух чисел. Список искомых чисел предлагается как входной параметр для функции comnodlist. Эта функция возвращает НОД для всех элементов своего входного параметра. В случае пустого списка или наличия в списке нецелых (нечисловых) - элементов - возвращает 0.

to comnodlist :l
if not numlist :l [op 0]
name first :l "d
name 2 "i
repeat (count :l) - 1 [ name nod :d item :i :l "d
name :i + 1 "i]
op :d
end

4.4. Наименьшее Общее Кратное (НОК)

Функция для вычисления наименьшего общего кратного двух чисел использует формулу:
НОК (х, у ) = х * у / НОК (х, у)
Для уменьшения вероятности переполнения - сначала выполняем деление, а затем умножение. Функция nok реализует этот алгоритм.

to nok :x :y
name nod :x :y "t
if :t = 0 [op 0]
op :x / :t * :y
end

Функция comlistnok возвращает НОК - общее для всех элементов входного списка; в случае нечислового списка - возвращает 0.

to comlistnok :l
if not numlist :l [op 0]
name 1 "t
name 1 "i
repeat count :l [name nok :t item :i :l "t
name :i + 1 "i]
op :t
end