Пример 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 не предусмотрена.

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

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

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

Пример программной реализации трехмерной операции

Из книги КОМПАС-3D V10 на 100 % автора Кидрук Максим Иванович

Пример программной реализации трехмерной операции Рассмотрим выполнение трехмерной формообразующей операции вручную (то есть в самом КОМПАС) и с помощью воображаемого подключаемого модуля. В качестве примера выберем обычную операцию выдавливания на основе несложного


Пример

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

Пример Программа в листинге 6.1 создает очередь сообщений, помещает в нее сообщение с 1 байтом информации, вызывает функцию msgctl с командой IPC_STAT, выполняет команду ipcs, используя функцию system, а затем удаляет очередь, вызвав функцию msgctl с командой IPC_RMID.Листинг 6.1.[1] Пример


Пример

Из книги Технологии программирования автора Камаев В А

Пример В листинге 6.21 приведен текст программы, которая определяет четыре ограничения, показанные в табл. 6.2.Листинг 6.21. Определение системных ограничений для очередей сообщений System V//svmsg/limits.c1  #include "unpipc.h"2  #define MAX_DATA 64*10243  #define MAX_NMESG 40964  #define MAX_NIDS 40965  int max_mesg;6  struct mymesg


Пример

Из книги Разработка приложений в среде Linux. Второе издание автора Джонсон Майкл К.

Пример Легче всего продемонстрировать проблему нашей реализации из предыдущего раздела с помощью примера. На рис. 8.1 изображена временная диаграмма выполнения нашей программы, а текст самой программы приведен в листинге 8.9.  Рис. 8.1. Временная диаграмма выполнения


Пример

Из книги Firebird РУКОВОДСТВО РАЗРАБОТЧИКА БАЗ ДАННЫХ автора Борри Хелен

Пример Вернемся к нашему примеру из листинга 9.2 и перепишем функции my_lock и my_unlock из листинга 9.1 так, чтобы воспользоваться блокировкой записей Posix. Текст этих функций приведен в листинге 9.3.Листинг 9.3. Блокировка записей fcntl по стандарту Posix//lock/lockfcntl.c1  #include


8.5.1. Пример

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

8.5.1. Пример В качестве очень простого, но все же информативного примера создадим библиотеку, содержащую одну короткую функцию. Ниже показано содержимое файла libhello.c.1: /* libhello.c */2:3: #include <stdio.h>4:5: void print_hello (void) {6:  printf("Добро пожаловать в библиотеку! ");7: }Разумеется, необходима


27.1.1. Пример

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

27.1.1. Пример В главе 8 был представлен пример использования обычной разделяемой библиотеки. Библиотеку libhello.so, которую нам удалось создать, можно загружать во время выполнения. Программа loadhello загружает libhello.so динамически и вызывает функцию print_hello, которая находится в


Пример

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

Пример В некоторой базе данных есть домен SYSUSER, размером до 31 символа, имеющий значение по умолчанию, получаемое из контекстной переменной CURRENT_USER:CREATE DOMAIN SYSUSER AS VARCHAR(31) DEFAULT CURRENT_USER;Объявляемая таблица содержит столбец UPDATED_BY, который использует доменSYSUSER:CREATE TABLE LOANS (LOAN_DATE


Пример 9-3. Еще один пример ограничения времени ожидания ввода от пользователя

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

Пример 9-3. Еще один пример ограничения времени ожидания ввода от пользователя #!/bin/bash# timeout.sh# Автор: Stephane Chazelas,# дополнен автором документа.INTERVAL=5 # предел времени ожиданияtimedout_read() { timeout=$1 varname=$2 old_tty_settings=`stty -g` stty -icanon min 0 time ${timeout}0 eval read $varname # или просто read $varname


Пример 10-27. Простой пример сравнения строк

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

Пример 10-27. Простой пример сравнения строк #!/bin/bash# match-string.sh: простое сравнение строкmatch_string (){ MATCH=0 NOMATCH=90 PARAMS=2 # Функция требует два входных аргумента. BAD_PARAMS=91 [ $# -eq $PARAMS ] || return $BAD_PARAMS case "$1" in "$2") return $MATCH;; * ) return $NOMATCH;; esac}a=oneb=twoc=threed=twomatch_string $a # неверное число


Пример 12-20. Пример форматирования списка файлов в каталоге

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

Пример 12-20. Пример форматирования списка файлов в каталоге #!/bin/bash# За основу сценария взят пример "man column".(printf "PERMISSIONS LINKS OWNER GROUP SIZE DATE TIME PROG-NAME " ; ls -l | sed 1d) | column -t# Команда "sed 1d" удаляет первую строку, выводимую командой ls,#+ (для локали "С" это строка: "total N",#+ где "N" -- общее


Пример 12-45. Пример работы с m4

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

Пример 12-45. Пример работы с m4 #!/bin/bash# m4.sh: Демонстрация некоторых возможносией макропроцессора m4# Строкиstring=abcdA01echo "len($string)" | m4 # 7echo "substr($string,4)" | m4 # A01echo "regexp($string,[0-1][0-1],&Z)" | m4 # 01Z# Арифметикаecho "incr(22)" | m4 # 23echo "eval(99 / 3)" | m4 #


Пример 24-2. Еще один пример проверки аргументов с помощью "И-списков"

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

Пример 24-2. Еще один пример проверки аргументов с помощью "И-списков" #!/bin/bashARGS=1 # Ожидаемое число аргументов.E_BADARGS=65 # Код завершения, если число аргументов меньше ожидаемого.test $# -ne $ARGS && echo "Порядок использования: `basename $0` $ARGS аргумент(а)(ов)" && exit $E_BADARGS# Если