Урок 2

Поиск простых чисел

На этом уроке мы создадим скриптовую функцию, которая будет подсчитывать количество простых делителей целого числа, и посчитаем, сколько простых чисел в интервале от 1 до 100.

Отступление. Вспомним, что целое положительное число называется простым, если оно не делится без остатка ни на какое другое целое число, кроме 1 и самого себя. Вспомним также, что делитель числа не может превышать половину самого числа.

Любой алгоритм удобнее отлаживать в основном теле скрипта, а не в процедуре. Сначала напишем скрипт, который подсчитывает количество простых делителей одного конкретного числа, например 12. Многие алгоритмы пишутся интуитивно, или, исходя из накопленного опыта и объяснить, как появился тот или другой алгоритм бывает довольно трудно. Поэтому предложим готовый алгоритм и дадим к нему некоторые пояснения.

x=12
count=0
i=2
repeat
  breakif i > x/2
  mod=(x % i)
  if mod=0
    count=count+1
    x=x/i 
  else
    i=i+1  
if count>0
  count=count+1

Итак, переменной x присвоим тестируемое число 12, а в дальнейшем, по мере поиска делителей в этой переменной будет храниться остаток деления исходного числа на все найденные делители. В переменной i будут содержаться значения тестируемых делителей. Поиск делителей начинаем с числа 2.

Тестирование делителей будет производится в цикле repeat. В теле цикла сначала ставим условия выхода из цикла: цикл обрывается, если очередной тестируемый делитель i превысит половину тестируемого числа x.

Переменная mod – это остаток деления тестируемого числа на тестируемый делитель. Если этот остаток равен нулю, то значение i является делителем для значения x. В этом случае мы наращиваем на единицу счетчик count и делим тестируемое число на найденный делитель. Если остаток mod не равен нулю, то значение тестируемого делителя i наращиваем на единицу.

После завершения цикла проверяем, а были ли найдены делители? Если были найдены, то получившееся значение x, при котором цикл был оборван, тоже является делителем исходного числа, и счётчик делителей в таком случае наращиваем на единицу. Наберите предложенный скрипт в программе и пройдите в шаговом режиме

Поиск простых чисел

Обратите внимание, что в цикле было найдено два делителя: 2 и ещё раз 2, после чего цикл был оборван оператором breakif. При этом x имело значение 3 – результат деления 12 на 2 и ещё раз на 2. Это значение тоже является делителем числа 12, поэтому общее значение делителей было увеличено на единицу и составило 3.

Проверьте, как срабатывает скрипт при разных значениях x: 7,21,99,1024. Должны получиться значения 0, 2, 3, 10. Теперь оформим алгоритм расчёта количества делителей в виде скриптовой функции и, проверим работу этой функции. Вспомним, что все локальные переменные в теле функции и формальные параметры функции должны начинаться с символа подчёрк. Добавим слева к названиям всех переменных символ подчёрка. Впереди вставим строку с ключевым словом function, названием функции дадим «DivCount», а формальным параметром будет тестируемая переменная _x. Телу функции придадим отступ слева, равный 2-м позициям., а тело функции должно иметь отступ от левого края равный 2. Завершим функцию строкой с ключевым словом «return» и переменной _count, в которой к моменту завершения работы функции должно быть количество простых делителей.

function DivCount(_x)
  _count=0
  _i=2
  repeat
    breakif _i > _x/2
    _mod=(_x % _i)
    if _mod=0
      _count=_count+1
      _x=_x/_i 
    else
      _i=_i+1  
  if _count>0
    _count=_count+1
  return _count

Основное тело скрипта (перед строками функции) будет состоять из вызова функции DivCount и оператора stop.

n=DivCount(12)
stop

Cтартуйте скрипт.

Поиск простых чисел

Результат тот же: Число 12 имеет 3 простых делителя.

Задание для самостоятельной работы: Посчитайте количество простых чисел в интервале от 2 до 100.

Поиск простых чисел

Наблюдаем результат: количество простых чисел в интервале от 1 до 100 равно 25.