diff options
author | yugui <yugui@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2008-09-03 13:57:21 +0000 |
---|---|---|
committer | yugui <yugui@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2008-09-03 13:57:21 +0000 |
commit | fce093432eadc191b3647f116a9c2f6748efda3e (patch) | |
tree | 08292b34a1435b87391cf0c11e042fca14443d00 /lib/mathn.rb | |
parent | 9cab7d15ca791d0b14db03217485a7c756097a71 (diff) |
* lib/mathn.rb (Integer): moved into prime.rb.
(Prime): ditto.
* lib/prime.rb (Integer): moved from mathn.rb.
(Integer.each_prime): added.
(Integer#prime?): added.
(Prime): moved from mathn.rb.
Its implmentation was rewritten. see [ruby-dev:35863].
And patched by Keiju ISHITSUKA <keiju@ishitsuka.com>,
see [ruby-dev:36128].
(Prime.new): obsolete.
(Prime.instance): added.
(Prime.each): added.
(Prime.int_from_prime_division): added.
(Prime.prime_division): added.
(Prime.prime?): added.
Patch by TOYOFUKU Chikanobu
<nobu_toyofuku at nifty.com> in [ruby-dev:36067].
(Prime.cache): removed.
(Prime.primes): removed.
(Prime.primes_so_far): removed.
(Prime#int_from_prime_division): added.
(Prime#prime_division): added.
(Prime#prime?): added.
(Prime#primes): removed.
(Prime#primes_so_far): removed.
(Prime::PseudoPrmeGenerator): added.
(Prime::EratosthenesGenerator): added.
(Prime::TrialDivisionGenerator): added.
(Prime::Generator23): added.
(Prime::TrialDivision): added.
Extracted from the previous implementation of Prime
by Keiju ISHITSUKA.
(Prime::EratosthenesSieve): added.
* lib/.document (prime.rb): added
* lib/README (prime.rb): added
* test/test_prime.rb: added.
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@19095 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
Diffstat (limited to 'lib/mathn.rb')
-rw-r--r-- | lib/mathn.rb | 96 |
1 files changed, 1 insertions, 95 deletions
diff --git a/lib/mathn.rb b/lib/mathn.rb index ce1acc927f..2af2b83da3 100644 --- a/lib/mathn.rb +++ b/lib/mathn.rb @@ -12,101 +12,7 @@ require "complex.rb" require "rational.rb" require "matrix.rb" - -class Integer - - def Integer.from_prime_division(pd) - value = 1 - for prime, index in pd - value *= prime**index - end - value - end - - def prime_division - raise ZeroDivisionError if self == 0 - ps = Prime.new - value = self - pv = [] - for prime in ps - 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 prime * prime >= value - end - if value > 1 - pv.push [value, 1] - end - return pv - end -end - -class Prime - include Enumerable - # These are included as class variables to cache them for later uses. If memory - # usage is a problem, they can be put in Prime#initialize as instance variables. - - # There must be no primes between @@primes[-1] and @@next_to_check. - @@primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101] - # @@next_to_check % 6 must be 1. - @@next_to_check = 103 # @@primes[-1] - @@primes[-1] % 6 + 7 - @@ulticheck_index = 3 # @@primes.index(@@primes.reverse.find {|n| - # n < Math.sqrt(@@next_to_check) }) - @@ulticheck_next_squared = 121 # @@primes[@@ulticheck_index + 1] ** 2 - - class << self - # Return the prime cache. - def cache - return @@primes - end - alias primes cache - alias primes_so_far cache - end - - def initialize - @index = -1 - end - - # Return primes given by this instance so far. - def primes - return @@primes[0, @index + 1] - end - alias primes_so_far primes - - def succ - @index += 1 - while @index >= @@primes.length - # Only check for prime factors up to the square root of the potential primes, - # but without the performance hit of an actual square root calculation. - if @@next_to_check + 4 > @@ulticheck_next_squared - @@ulticheck_index += 1 - @@ulticheck_next_squared = @@primes.at(@@ulticheck_index + 1) ** 2 - end - # Only check numbers congruent to one and five, modulo six. All others - # are divisible by two or three. This also allows us to skip checking against - # two and three. - @@primes.push @@next_to_check if @@primes[2..@@ulticheck_index].find {|prime| @@next_to_check % prime == 0 }.nil? - @@next_to_check += 4 - @@primes.push @@next_to_check if @@primes[2..@@ulticheck_index].find {|prime| @@next_to_check % prime == 0 }.nil? - @@next_to_check += 2 - end - return @@primes[@index] - end - alias next succ - - def each - return to_enum(:each) unless block_given? - loop do - yield succ - end - end -end +require "prime.rb" class Fixnum remove_method :/ |