e$B$1$$$8$e!w$$$7$D$+$G$9e(B.
e$B$J$s$+e(B, e$BAw$C$?%a%$%k$,%9%Q%`07$$$K$J$C$?$h$&$J$N$Ge(B,
e$B:FAw$7$^$9e(B.
yuguie$B$5$s$N$H$O0U?^$7$F$$$k$H$3$m$OBgBNF1$8$@$H;W$$$^$9$,e(B…
In [ruby-dev :35883 ] the message: "[ruby-dev:35883] Re: Refactoring
of enumerating prime numbers ", on Aug/20 12:13(JST) Nobuyoshi N.
writes:
e$B$J$+$@$G$9!#e(B
e$B;d$b$=$&$J$N$+$J$!e(B? e$B$H;W$$$D$D$be(B, e$B$G$Oe(B, e$B85$N%/%i%9$NL>A0$O$I$&$9$k$s$@e(B?
e$B$H;W$C$?$j$b$7$F$^$9e(B.
class << (Prime = Object.new); end e$B$G!#e(B
e$B$=$l$b9M$($?$s$G$9$,e(B… Generator e$B$HMm$_$^$9$N$Ge(B,
e$B$=$A$i$Ge(B.
Enumerablee$B$OF~$lK:$l$G$9$,!"e(BGeneratore$B$N$h$&$KJL%/%i%9$r2p$9$kI,e(B
e$BMW$O$J$$$N$G$O$J$$$+$H$$$&$3$H$G$9!#e(B
Generatore$B$,0l<oN`$J$i$=$l$O8@$($k$H;W$&$N$G$9$,e(B,
e$BK-J!$5$s$N%a%$%k$N$he(B
e$B$&$Ke(B,e$BC1D4A}2C$G>/$J$/$H$b$9$Y$F$NAG?t$,4^$^$l$k?tNs$rMQ$$$kJ}$,NI$$>le(B
e$B9g$b$"$k$N$Ge(B, Generator e$B$Oe(B
e$BJL$K$"$C$?J}$,$h$$5$$,$7$F$$$^$9e(B.
e$B$=$l$,e(BPrimee$B<+?H$NLr3d$J$s$8$c$J$$$+$J$!$H!#e(B
e$B;d$,8@$$$?$+$C$?$3$H$H$A$g$C$H$:$l$F$k$+$be(B.
e$B>$7$/$OE:IU$N%3!<%I$r8+$Fe(B
e$B$$$?$@$-$?$$$N$G$9$,e(B, @@class_var
e$B$,B?MQ$5$l$F$$$k$N$,5$$K$/$o$J$$$N$Ge(B,
e$B$=$l$r$J$/$7$?$+$C$?$N$G$9e(B.
e$B$^$?e(B, e$BHyL/$K%9%l%C%I%;!<%U$G$J$$5$$b$7$?$j$b$7$F$$$k$N$Ge(B, e$B$=$3$b2r>C$Ge(B
e$B$-$l$P$J$!e(B. e$B$J$I$H;W$C$?$j$7$F$$$^$9e(B
e$B$=$3$OLdBj$G$9$M!#e(BPrime#succe$B$N%k!<%W$re(Bsynchronizee$B$5$;$l$P$$$$$Ge(B
e$B$7$g$&$+!#e(B
e$B$$$C$F$*$$$Fe(B, e$B2?$J$s$G$9$,e(B(^^;;
rubye$B$N%i%$%V%i%j$O$[$H$s$I$,%9%l%C%I%;!<e(B
e$B%U$G$J$$$N$Ge(B, e$B5$$K$7$J$/$F$b$h$$5$$K$J$C$F$$$^$9e(B.
e$B?70Fe(B:
-
Primee$B%/%i%9$Oe(B singleton.
-
Primee$B%/%i%9%a%=%C%I$O%$%s%9%?%s%9%a%=%C%I$K%G%l%2!<%H$9$ke(B.
-
Prime::Generator
e$BAG?tNs$Ne(Bgenerator
-
Prime::Generator23
e$BK-J!$5$s$Ne(Bgenerator.
e$BL>A0$NM3Mhe(B: 2e$B$He(B3e$B$NG?t0J30$N?tCM$J$N$Ge(B.
-
Prime::IncreaseSuperPrimeGenerator
e$B>e5-e(B2e$B$D$Ne(Bgeneratore$B$NCj>]%9!<%Q!<%/%i%9e(B
e$BL>A0$O$$$^$$$A$J$s$G$9$,e(B, e$B>:=g$Ge(B,
e$BAG?t=89g$N%9!<%Q!<%;%C%H$K$J$ke(B
generator e$B$H$$$&$3$H$m$+$i$H$C$F$$$^$9e(B.
e$B$h$$L>A0Jg=8Cfe(B
-
Prime::PrimeSet
e$BAG?t@8@.$NK\BNe(B
singletone$B$K$9$k$3$H$K$h$C$Fe(B, e$B%/%i%9JQ?t$r$J$/$7$F$$$^$9e(B
-
Integer e$B$KDI2C$5$l$k%a%=%C%Ie(B
e$B<BAu$Oe(B, Primee$B$NJ}$K0\F0e(B
-
Prime#prime_division. Prime.prime?
generator e$B$,;XDj$G$-$k$h$&$K$7$F$"$j$^$9e(B.
e$BC1H/$K;H$&$J$iK-J!$5$s$NJ}e(B
e$B$,Aa$$$H;W$$$^$9$,e(B, e$B%-%c%C%7%e$N8z2L$,$G$k$3$H$b$"$k$N$Ge(B,
e$B;H$$J}$K$h$Ce(B
e$B$FJQ$($i$l$k$h$&$K$H8@$&0U?^$G$9e(B
e$B$s$Ge(B, e$B%3!<%I$O0J2<$N46$8$K$J$C$F$$$^$9e(B.
e$B$40U8+Jg=8Cfe(B!!
– prime.rb
require “singleton”
require “forwardable”
class Integer
def Integer.from_prime_division(pd)
Prime.int_from_prime_division(pd)
end
def prime_division(generator = Prime::Generator23.new)
Prime.prime_division(self, generator)
end
def prime?
Prime.prime?(self)
end
end
class Prime
include Singleton
include Enumerable
class<<self
extend Forwardable
include Enumerable
def method_added(method)
#puts "method add: #{method}"
(class<<self;self;end).def_delegator :instance, method
end
end
def each(&block)
Generator.new.each(&block)
end
def prime?(value, generator = Prime::Generator23.new)
for num in generator
return false if value % num == 0
return true if value > num * num
end
end
def int_from_prime_division(pd)
pd.inject(1){|value, (prime, index)|
value *= prime**index
}
end
def prime_division(value, generator= Prime::Generator23.new)
raise ZeroDivisionError if self == 0
pv = []
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 prime * prime >= value
end
if value > 1
pv.push [value, 1]
end
return pv
end
class IncreaseSuperPrimeGenerator
include Enumerable
def succ
raise NotImplementedError, "need to define `succ'"
end
def each(&block)
return self unless block
loop do
block.call succ
end
end
end
ISPG = IncreaseSuperPrimeGenerator
class Generator<ISPG
def initialize
@index = -1
end
def succ
PrimeSet.instance[@index += 1]
end
alias next succ
end
class Generator23<ISPG
def initialize
@prime = 1
@step = nil
end
def succ
loop do
if (@step)
@prime += @step
@step = 6 - @step
else
case @prime
when 1; @prime = 2
when 2; @prime = 3
when 3; @prime = 5; @step = 2
end
end
return @prime
end
end
end
class PrimeSet
include Singleton
def initialize
# 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
end
# Return the prime cache.
def cache
return @primes
end
alias primes cache
alias primes_so_far cache
def [](index)
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
end
end
__
---------------------------------------------------->> e$B@PDMe(B
e$B7=<ye(B <<—
---------------------------------->> e-mail: [email protected] <<—