класс Prime

Родитель:: Объект
Включенные модули:: Enumerable, Singleton

Множество всех простых чисел.

Пример

Prime.each(100) do |prime|
  p prime  #=> 2, 3, 5, 7, 11, ...., 97
end

Prime это Enumerable:

Prime.first 5 # => [2, 3, 5, 7, 11]

Получение экземпляра

Для удобства каждый метод экземпляра Prime.instance может быть использован как метод класса Prime.

Например:

Prime.instance.prime?(2)  #=> true
Prime.prime?(2)           #=> true

Генераторы

«Генератор» предоставляет реализацию для перечисления псевдопростых чисел и запоминает позицию перечисления и верхнюю границу. Кроме того, это внешний итератор перечисления простых чисел, совместимый с Enumerator.

Prime::PseudoPrimeGenerator — базовый класс для генераторов. Существует несколько реализаций генератора.

Prime::EratosthenesGenerator: Использует решето Эратосфена.
Prime::TrialDivisionGenerator: Использует метод пробного деления.
Prime::Generator23: Генерирует все положительные целые числа, которые не делятся ни на 2, ни на 3. Эта последовательность очень плоха в качестве последовательности псевдопростых чисел. Но она быстрее и использует меньше памяти, чем другие генераторы. Поэтому она подходит для факторизации целого числа, которое не очень велико, но имеет много простых множителей. Например, для Prime#prime?.

Константы

VERSION

Открытые методы экземпляров

each(ubound = nil, generator = EratosthenesGenerator.new, &block) Показать исходный код

# File lib/prime.rb, line 139
def each(ubound = nil, generator = EratosthenesGenerator.new, &block)
  generator.upper_bound = ubound
  generator.each(&block)
end

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

Параметры

ubound: Необязательно. Произвольное положительное число. Верхняя граница перечисления. Метод перечисляет простые числа бесконечно, если ubound равно nil.
generator: Необязательно. Реализация генератора псевдопростых чисел.

Возвращаемое значение

Вычисленное значение переданного блока в последний раз. Или перечислитель, совместимый с Enumerator, если блок не указан.

Описание

Вызывает block один раз для каждого простого числа, передавая простое число в качестве параметра.

ubound: Верхняя граница простых чисел. Итератор останавливается после того, как он сгенерирует все простые числа p ≤ ubound.

int_from_prime_division(pd) Показать исходный код

# File lib/prime.rb, line 175
def int_from_prime_division(pd)
  pd.inject(1){|value, (prime, index)|
    value * prime**index
  }
end

Восстанавливает факторизацию по простым числам и возвращает произведение.

Параметры

pd: Array пар целых чисел. Каждая внутренняя пара состоит из простого числа — простого множителя — и натурального числа — показателя степени.

Пример

Для [[p_1, e_1], [p_2, e_2], ...., [p_n, e_n]], он возвращает:

p_1**e_1 * p_2**e_2 * .... * p_n**e_n.

Prime.int_from_prime_division([[2,2], [3,1]])  #=> 12

простое?(значение, генератор = Prime::Generator23.new) Показать исходный код

# File lib/prime.rb, line 151
def prime?(value, generator = Prime::Generator23.new)
  raise ArgumentError, "Expected a prime generator, got #{generator}" unless generator.respond_to? :each
  raise ArgumentError, "Expected an integer, got #{value}" unless value.respond_to?(:integer?) && value.integer?
  return false if value < 2
  generator.each do |num|
    q,r = value.divmod num
    return true if q < num
    return false if r == 0
  end
end

Возвращает true, если value является простым числом, иначе возвращает false.

Параметры

value: Произвольное целое число для проверки.
generator: Необязательно. Генератор псевдопростых чисел.

факторизация_по_простым_числам(значение, генератор = Prime::Generator23.new) Показать исходный код

# File lib/prime.rb, line 205
def prime_division(value, generator = Prime::Generator23.new)
  raise ZeroDivisionError if value == 0
  if value < 0
    value = -value
    pv = [[-1, 1]]
  else
    pv = []
  end
  generator.each do |prime|
    count = 0
    while (value1, mod = value.divmod(prime)
           mod) == 0
      value = value1
      count += 1
    end
    if count != 0
      pv.push [prime, count]
    end
    break if value1 <= prime
  end
  if value > 1
    pv.push [value, 1]
  end
  pv
end

Возвращает факторизацию value.

Параметры

value: Произвольное целое число.
generator: Необязательно. Генератор псевдопростых чисел. generator.succ должен возвращать следующее псевдопростое число в порядке возрастания. Он должен генерировать все простые числа, но может также генерировать и составные числа.

Исключения

ZeroDivisionError: если value равно нулю.

Пример

Для произвольного целого числа:

n = p_1**e_1 * p_2**e_2 * .... * p_n**e_n,

prime_division(n) возвращает:

[[p_1, e_1], [p_2, e_2], ...., [p_n, e_n]].

Prime.prime_division(12) #=> [[2,2], [3,1]]

Ruby Core © 1993–2017 Yukihiro Matsumoto
Licensed under the Ruby License.
Ruby Standard Library © contributors
Licensed under their own licenses.