класс 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?.

Методы экземпляра (public)

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

# File lib/prime.rb, line 135
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 171
def int_from_prime_division(pd)
  pd.inject(1){|value, (prime, index)|
    value * prime**index
  }
end

Восстанавливает разложение на простые множители и возвращает произведение.

Параметры

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

Пример

Для [[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?(value, generator = Prime::Generator23.new) Показать исходный код

# File lib/prime.rb, line 147
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_division(value, generator = Prime::Generator23.new) Показать исходный код

# File lib/prime.rb, line 201
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.