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

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

  1. #!/bin/bash
  2. # primes.sh: Генерация простых чисел, без использования массивов.
  3. # Автор: Stephane Chazelas.
  4. #  Этот сценарий не использует класический алгоритм "Решето Эратосфена",
  5. #+ вместо него используется более понятный метод проверки каждого кандидата в простые числа
  6. #+ путем поиска делителей, с помощью оператора нахождения остатка от деления "%".
  7. LIMIT=1000                    # Простые от 2 до 1000
  8. Primes()
  9. {
  10.  (( n = $1 + 1 ))             # Перейти к следующему числу.
  11.  shift                        # Следующий параметр в списке.
  12. #  echo "_n=$n i=$i_"
  13.  if (( n == LIMIT ))
  14.  then echo $*
  15.  return
  16.  fi
  17.  for i; do                    # "i" устанавливается в "@", предыдущее значение $n.
  18. #   echo "-n=$n i=$i-"
  19.    (( i * i > n )) && break   # Оптимизация.
  20.    (( n % i )) && continue    # Отсечь составное число с помощью оператора "%".
  21.    Primes $n $@               # Рекурсивный вызов внутри цикла.
  22.    return
  23.    done
  24.    Primes $n $@ $n            # Рекурсивный вызов за пределами цикла.
  25.                               # Последовательное накопление позиционных параметров.
  26.                               # в "$@" накапливаются простые числа.
  27. }
  28. Primes 1
  29. exit 0
  30. # Раскомментарьте строки 16 и 24, это поможет понять суть происходящего.
  31. # Сравните скоростные характеристики этого сценария и сценария (ex68.sh),
  32. # реализующего алгоритм "Решето Эратосфена".
  33. # Упражнение: Попробуйте реализовать этот сценарий без использования рекурсии.
  34. #             Это даст некоторый выигрыш в скорости.