Пример A-18. Генерация простых чисел, с использованием оператора деления по модулю (остаток от деления)

Пример A-18. Генерация простых чисел, с использованием оператора деления по модулю (остаток от деления)

#!/bin/bash

# primes.sh: Генерация простых чисел, без использования массивов.

# Автор: Stephane Chazelas.

# Этот сценарий не использует класический алгоритм "Решето Эратосфена",

#+ вместо него используется более понятный метод проверки каждого кандидата в простые числа

#+ путем поиска делителей, с помощью оператора нахождения остатка от деления "%".

LIMIT=1000 # Простые от 2 до 1000

Primes()

{

(( n = $1 + 1 )) # Перейти к следующему числу.

shift # Следующий параметр в списке.

# echo "_n=$n i=$i_"

if (( n == LIMIT ))

then echo $*

return

fi

for i; do # "i" устанавливается в "@", предыдущее значение $n.

# echo "-n=$n i=$i-"

(( i * i > n )) && break # Оптимизация.

(( n % i )) && continue # Отсечь составное число с помощью оператора "%".

Primes $n $@ # Рекурсивный вызов внутри цикла.

return

done

Primes $n $@ $n # Рекурсивный вызов за пределами цикла.

# Последовательное накопление позиционных параметров.

# в "$@" накапливаются простые числа.

}

Primes 1

exit 0

# Раскомментарьте строки 16 и 24, это поможет понять суть происходящего.

# Сравните скоростные характеристики этого сценария и сценария (ex68.sh),

# реализующего алгоритм "Решето Эратосфена".

# Упражнение: Попробуйте реализовать этот сценарий без использования рекурсии.

# Это даст некоторый выигрыш в скорости.

+

Jordi Sanfeliu дал согласие на публикацию своего сценария tree.

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг

У11.9 Генерация случайных чисел

Из книги UNIX: взаимодействие процессов автора Стивенс Уильям Ричард

У11.9 Генерация случайных чисел Напишите класс, реализующий алгоритм получения псевдослучайных чисел, основанный на последовательности: ni = f(ni - 1), где функция f задана, а начальное значение n0 определяется клиентом класса. Функция не должна иметь побочных эффектов.


Пример: уведомление с использованием sigwait вместо обработчика

Из книги Этюды для программистов [неполностью, главы 1–24] автора Уэзерелл Чарлз

Пример: уведомление с использованием sigwait вместо обработчика Хотя программа из предыдущего примера работает правильно, можно повысить ее эффективность. Программа использует sigsuspend для блокировки в ожидании прихода сообщения. При помещении сообщения в пустую очередь


15. Проще простого, или Поиск узоров из простых чисел

Из книги VBA для чайников автора Каммингс Стив

15. Проще простого, или Поиск узоров из простых чисел Всякий, кто изучает простые числа, бывает очарован ими и одновременно ощущает собственное бессилие. Определение простых чисел так просто и очевидно; найти очередное простое число так легко; разложение на простые


Пример оператора Select Case

Из книги C++. Сборник рецептов автора Диггинс Кристофер

Пример оператора Select Case Здесь явно не помешает пример, показывающий, как в действительности может выглядеть структура Select Case. Select Case objRol l OfFi l m.Type Case "Слайдовая" intСлайдовые = intСлайдовые + 1 Case "Цветная негативная" intЦветныеНегативные =


11.6. Генерация случайных чисел

Из книги Фундаментальные алгоритмы и структуры данных в Delphi автора Бакнелл Джулиан М.

11.6. Генерация случайных чисел ПроблемаТребуется сгенерировать несколько случайных чисел в формате с плавающей точкой в интервале значений [0.0, 1.0) при равномерном их распределении.РешениеСтандарт C++ предусматривает наличие C-функции библиотеки этапа исполнения rand,


Генерация случайных чисел

Из книги Искусство программирования на языке сценариев командной оболочки автора Купер Мендель

Генерация случайных чисел Прежде всего, давайте опишем, что мы понимаем под случайным числом (random number). Без четкого определения термина мы будем неуверенно себя чувствовать при разработке и реализации генератора случайных чисел.Будет ли число 2 случайным числом? Просто


9.6. $RANDOM: генерация псевдослучайных целых чисел

Из книги Язык Си - руководство для начинающих автора Прата Стивен

9.6. $RANDOM: генерация псевдослучайных целых чисел $RANDOM -- внутренняя функция Bash (не константа), которая возвращает псевдослучайные целые числа в диапазоне 0 - 32767. Функция $RANDOM не должна использоваться для генераци ключей


Пример 9-23. Генерация случайных чисел

Из книги Цифровой журнал «Компьютерра» № 210 автора Журнал «Компьютерра»

Пример 9-23. Генерация случайных чисел #!/bin/bash# $RANDOM возвращает различные случайные числа при каждом обращении к ней.# Диапазон изменения: 0 - 32767 (16-битовое целое со знаком).MAXCOUNT=10count=1echoecho "$MAXCOUNT случайных чисел:"echo "-----------------"while [ "$count" -le $MAXCOUNT ] # Генерация 10 ($MAXCOUNT) случайных


Пример 22-3. Наибольшее из двух чисел

Из книги автора

Пример 22-3. Наибольшее из двух чисел #!/bin/bash# max.sh: Наибольшее из двух целых чисел.E_PARAM_ERR=-198 # Если функции передано меньше двух параметров.EQUAL=-199 # Возвращаемое значение, если числа равны.max2 () # Возвращает наибольшее из двух чисел.{ # Внимание: сравниваемые


Пример 22-4. Преобразование чисел в римскую форму записи

Из книги автора

Пример 22-4. Преобразование чисел в римскую форму записи #!/bin/bash# Преобразование чисел из арабской формы записи в римскую# Диапазон: 0 - 200# Расширение диапазона представляемых чисел и улучшение сценария# оставляю вам, в качестве упражнения.# Порядок использования: roman


Пример 22-6. Сравнение двух больших целых чисел

Из книги автора

Пример 22-6. Сравнение двух больших целых чисел #!/bin/bash# max2.sh: Наибольшее из двух БОЛЬШИХ целых чисел.# Это модификация предыдущего примера "max.sh",# которая позволяет выполнять сравнение больших целых чисел.EQUAL=0 # Если числа равны.MAXRETVAL=255 # Максимально возможное


Операция деления: /

Из книги автора

Операция деления: /      В языке Си символ / указывает на операцию деления. Величина, стоящая слева от этого знака, делится на величину, расположенную справа от него. Например, в результате выполнения оператора: four = 12.0/3.0;переменной four будет присвоено значение 4.0. Заметим,


Операция деления по модулю: %

Из книги автора

Операция деления по модулю: %      Операция деления по модулю используется в целочисленной арифметикe. Ее результатом является остаток от деления целого числа, стоящего слева от знака операции, на число, расположенное справa от него. Например, 13 % 5 (читается как "13 по модулю


Новые деления на галактической линейке Дмитрий Вибе

Из книги автора

Новые деления на галактической линейке Дмитрий Вибе Опубликовано 27 января 2014 Расстояние — главный астрономический параметр. Без расстояния нет ни звёздной динамики, ни теории звёздной эволюции, ни космологии. Но измерить расстояние до объекта,