Class: Prime
- Extended by:
- Enumerable, Forwardable
- Includes:
- Enumerable
- Defined in:
- lib/vendor/backports-3.3.5/lib/backports/1.9.1/stdlib/prime.rb
Overview
The set of all prime numbers.
Example
Prime.each(100) do |prime|
p prime #=> 2, 3, 5, 7, 11, ...., 97
end
Retrieving the instance
Prime
.new is obsolete. Now Prime
has the default instance and you can access it as Prime
.instance.
For convenience, each instance method of Prime
.instance can be accessed as a class method of Prime
.
e.g.
Prime.instance.prime?(2) #=> true
Prime.prime?(2) #=> true
Generators
A “generator” provides an implementation of enumerating pseudo-prime numbers and it remembers the position of enumeration and upper bound. Futhermore, it is a external iterator of prime enumeration which is compatible to an Enumerator.
Prime
::PseudoPrimeGenerator
is the base class for generators. There are few implementations of generator.
Prime
::EratosthenesGenerator
-
Uses eratosthenes’s sieve.
Prime
::TrialDivisionGenerator
-
Uses the trial division method.
Prime
::Generator23
-
Generates all positive integers which is not divided by 2 nor 3. This sequence is very bad as a pseudo-prime sequence. But this is faster and uses much less memory than other generators. So, it is suitable for factorizing an integer which is not large but has many prime factors. e.g. for Prime#prime? .
Defined Under Namespace
Modules: OldCompatibility Classes: EratosthenesGenerator, EratosthenesSieve, Generator23, PseudoPrimeGenerator, TrialDivision, TrialDivisionGenerator
Class Method Summary collapse
-
.instance ⇒ Object
Returns the default instance of Prime.
-
.method_added(method) ⇒ Object
:nodoc:.
Instance Method Summary collapse
-
#each(ubound = nil, generator = EratosthenesGenerator.new, &block) ⇒ Object
Iterates the given block over all prime numbers.
-
#initialize ⇒ Prime
constructor
obsolete.
-
#int_from_prime_division(pd) ⇒ Object
Re-composes a prime factorization and returns the product.
-
#prime?(value, generator = Prime::Generator23.new) ⇒ Boolean
Returns true if
value
is prime, false for a composite. -
#prime_division(value, generator = Prime::Generator23.new) ⇒ Object
Returns the factorization of
value
.
Methods included from Enumerable
chunk, count, cycle, drop, drop_while, each_entry, each_with_index_with_optional_args_and_block, each_with_object, entries_with_optional_arguments, find_index, first, flat_map, group_by, inject_with_symbol, lazy, max_by, min_by, minmax, minmax_by, none?, one?, reverse_each, slice_before, sum, take, take_while, to_a_with_optional_arguments
Constructor Details
#initialize ⇒ Prime
obsolete. Use Prime
::instance
or class methods of Prime
.
89 90 91 92 93 |
# File 'lib/vendor/backports-3.3.5/lib/backports/1.9.1/stdlib/prime.rb', line 89 def initialize @generator = EratosthenesGenerator.new extend OldCompatibility warn "Prime::new is obsolete. use Prime::instance or class methods of Prime." end |
Class Method Details
.instance ⇒ Object
Returns the default instance of Prime.
99 |
# File 'lib/vendor/backports-3.3.5/lib/backports/1.9.1/stdlib/prime.rb', line 99 def instance; @the_instance end |
.method_added(method) ⇒ Object
:nodoc:
101 102 103 |
# File 'lib/vendor/backports-3.3.5/lib/backports/1.9.1/stdlib/prime.rb', line 101 def method_added(method) # :nodoc: (class<< self;self;end).def_delegator :instance, method end |
Instance Method Details
#each(ubound = nil, generator = EratosthenesGenerator.new, &block) ⇒ Object
Iterates the given block over all prime numbers.
Parameters
ubound
-
Optional. An arbitrary positive number. The upper bound of enumeration. The method enumerates prime numbers infinitely if
ubound
is nil. generator
-
Optional. An implementation of pseudo-prime generator.
Return value
An evaluated value of the given block at the last time. Or an enumerator which is compatible to an Enumerator
if no block given.
Description
Calls block
once for each prime number, passing the prime as a parameter.
ubound
-
Upper bound of prime numbers. The iterator stops after yields all prime numbers p <=
ubound
.
Note
Prime
.new
returns a object extended by Prime
::OldCompatibility
in order to compatibility to Ruby 1.8, and Prime
#each is overwritten by Prime
::OldCompatibility
#each
.
Prime
.new
is now obsolete. Use Prime
.instance
.each
or simply Prime
.each
.
136 137 138 139 |
# File 'lib/vendor/backports-3.3.5/lib/backports/1.9.1/stdlib/prime.rb', line 136 def each(ubound = nil, generator = EratosthenesGenerator.new, &block) generator.upper_bound = ubound generator.each(&block) end |
#int_from_prime_division(pd) ⇒ Object
Re-composes a prime factorization and returns the product.
Parameters
pd
-
Array of pairs of integers. The each internal pair consists of a prime number – a prime factor – and a natural number – an exponent.
Example
For [[p_1, e_1], [p_2, e_2], .…, [p_n, e_n]], it returns p_1**e_1 * p_2**e_2 * .… * p_n**e_n.
Prime.int_from_prime_division([[2,2], [3,1]]) #=> 12
169 170 171 172 173 |
# File 'lib/vendor/backports-3.3.5/lib/backports/1.9.1/stdlib/prime.rb', line 169 def int_from_prime_division(pd) pd.inject(1){|value, (prime, index)| value *= prime**index } end |
#prime?(value, generator = Prime::Generator23.new) ⇒ Boolean
Returns true if value
is prime, false for a composite.
Parameters
value
-
an arbitrary integer to be checked.
generator
-
optional. A pseudo-prime generator.
147 148 149 150 151 152 153 154 155 |
# File 'lib/vendor/backports-3.3.5/lib/backports/1.9.1/stdlib/prime.rb', line 147 def prime?(value, generator = Prime::Generator23.new) value = -value if value < 0 return false if value < 2 for num in generator q,r = value.divmod num return true if q < num return false if r == 0 end end |
#prime_division(value, generator = Prime::Generator23.new) ⇒ Object
Returns the factorization of value
.
Parameters
value
-
An arbitrary integer.
generator
-
Optional. A pseudo-prime generator.
generator
.succ must return the next pseudo-prime number in the ascendent order. It must generate all prime numbers, but may generate non prime numbers.
Exceptions
ZeroDivisionError
-
when
value
is zero.
Example
For an arbitrary integer n = p_1**e_1 * p_2**e_2 * .… * p_n**e_n, prime_division(n) returns [[p_1, e_1], [p_2, e_2], .…, [p_n, e_n]].
Prime.prime_division(12) #=> [[2,2], [3,1]]
196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 |
# File 'lib/vendor/backports-3.3.5/lib/backports/1.9.1/stdlib/prime.rb', line 196 def prime_division(value, generator= Prime::Generator23.new) raise ZeroDivisionError if value == 0 if value < 0 value = -value pv = [[-1, 1]] else pv = [] end for prime in generator 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 return pv end |