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

Пример 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.

Оглавление книги