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

Пример 25-8. Пример реализации алгоритма Решето Эратосфена

Пример 25-8. Пример реализации алгоритма Решето Эратосфена

#!/bin/bash

# sieve.sh

# Решето Эратосфена

# Очень старый алгоритм поиска простых чисел.

# Этот сценарий выполняется во много раз медленнее

# чем аналогичная программа на C.

LOWER_LIMIT=1 # Начиная с 1.

UPPER_LIMIT=1000 # До 1000.

# (Вы можете установить верхний предел и выше... если вам есть чем себя занять.)

PRIME=1

NON_PRIME=0

declare -a Primes

# Primes[] -- массив.

initialize ()

{

# Инициализация массива.

i=$LOWER_LIMIT

until [ "$i" -gt "$UPPER_LIMIT" ]

do

Primes[i]=$PRIME

let "i += 1"

done

# Все числа в заданном диапазоне считать простыми,

# пока не доказано обратное.

}

print_primes ()

{

# Вывод индексов элементов массива Primes[], которые признаны простыми.

i=$LOWER_LIMIT

until [ "$i" -gt "$UPPER_LIMIT" ]

do

if [ "${Primes[i]}" -eq "$PRIME" ]

then

printf "%8d" $i

# 8 пробелов перед числом придают удобочитаемый табличный вывод на экран.

fi

let "i += 1"

done

}

sift () # Отсеивание составных чисел.

{

let i=$LOWER_LIMIT+1

# Нам известно, что 1 -- это простое число, поэтому начнем с 2.

until [ "$i" -gt "$UPPER_LIMIT" ]

do

if [ "${Primes[i]}" -eq "$PRIME" ]

# Не следует проверять вторично числа, которые уже признаны составными.

then

t=$i

while [ "$t" -le "$UPPER_LIMIT" ]

do

let "t += $i "

Primes[t]=$NON_PRIME

# Все числа, которые делятся на $t без остатка, пометить как составные.

done

fi

let "i += 1"

done

}

# Вызов функций.

initialize

sift

print_primes

# Это называется структурным программированием.

echo

exit 0

# ----------------------------------------------- #

# Код, приведенный ниже, не исполняется из-за команды exit, стоящей выше.

# Улучшенная версия, предложенная Stephane Chazelas,

# работает несколько быстрее.

# Должен вызываться с аргументом командной строки, определяющем верхний предел.

UPPER_LIMIT=$1 # Из командной строки.

let SPLIT=UPPER_LIMIT/2 # Рассматривать делители только до середины диапазона.

Primes=( '' $(seq $UPPER_LIMIT) )

i=1

until (( ( i += 1 ) > SPLIT )) # Числа из верхней половины диапазона могут не рассматриваться.

do

if [[ -n $Primes[i] ]]

then

t=$i

until (( ( t += i ) > UPPER_LIMIT ))

do

Primes[t]=

done

fi

done

echo ${Primes[*]}

exit 0

Сравните этот сценарий с генератором простых чисел, не использующим массивов, Пример A-18.

--

Массивы позволяют эмулировать некоторые структуры данных, поддержка которых в Bash не предусмотрена.

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