Integer#prime_division $B$H(B Prime

Ruby Development
#1

e$BK-J!$G$9!#e(B

((2**17-1)2).prime_division e$B$KHf$Y$Fe(B
((219-1)**2).prime_division
e$B$N;~4V$,0[MM$K$+$+$k$N$GD4$Y$?$H$3$me(B Integer#prime_division
e$B$NCf$Ne(B
ps = Prime.new
[email protected]@.$9$k$N$K%3%9%H$,$+$+$C$F$$$F!"$h$jC1=c$Je(B
ps = (2…n)
e$B$r;H$&J}$,B.$/$J$k$h$&$G$9!#e(B
e$B!J<BMQ$K$Oe(B 2,3e$B$He(B e$B!^e(B1(mod 6)
e$B$"$?$j$r;H$&$N$,$h$$$G$7$g$&$+!Ke(B

e$B$^$?e(B Prime e$B$Ne(B initialize e$B$He(B succ
e$B$b$h$jC1=c$K$7$?e(B

def initialize
@seed = 1
@primes = []
end

def succ
i = -1
size = @primes.size
while i < size
if i == -1
@seed += 1
i += 1
else
prime = @primes[i]
q,r = @seed.divmod(prime)
if r != 0
break if q <= prime
i += 1
else
i = -1
end
end
end
@primes.push @seed
return @seed
end

e$B$NJ}$,B.$/$J$k$h$&$G$9!#e(B

                    e$BK-J!e(B
                    [email protected]
#2

e$BK-J!$G$9!#e(B

ps = (2…n)
e$B$r;H$&J}$,B.$/$J$k$h$&$G$9!#e(B

n e$B$N$H$3$m$Oe(B self e$B$Ge(B

ps = (2…self)
e$B$G$7$?!#e(B

                    e$BK-J!e(B
                    [email protected]
#3

e$B$1$$$8$e!w$$$7$D$+$G$9e(B.

In [ruby-dev:30920] the message: “[ruby-dev:30920]
Integer#prime_division e$B$He(B Prime”, on Jun/07 18:11(JST) TOYOFUKU
Chikanobu writes:

e$BK-J!$G$9!#e(B

e$B$*5W$7$V$j$G$4$6$$$^$9e(B.

((2**17-1)2).prime_division e$B$KHf$Y$Fe(B ((219-1)**2).prime_division
e$B$N;~4V$,0[MM$K$+$+$k$N$GD4$Y$?$H$3$me(B Integer#prime_division
e$B$NCf$Ne(B
ps = Prime.new
[email protected]@.$9$k$N$K%3%9%H$,$+$+$C$F$$$F!"$h$jC1=c$Je(B
ps = (2…n)
e$B$r;H$&J}$,B.$/$J$k$h$&$G$9!#e(B

e$B$J$k$[$Ie(B, [email protected]$13d$j$-$C$F$$$k$N$Ge(B,
e$B$o$6$o$6AG?tNs$rMQ$$e(B
e$B$kI,MW$O$J$$$o$1$G$9$Me(B.

e$B!J<BMQ$K$Oe(B 2,3e$B$He(B e$B!^e(B1(mod 6) e$B$"$?$j$r;H$&$N$,$h$$$G$7$g$&$+!Ke(B

e$B$3$A$i$be(B,

for prime in ps
  count = 0
  while (value1, mod = value.divmod(prime)
   mod) == 0

value = value1
count += 1
end
if count != 0

e$B$H$J$C$F$$$^$9$N$Ge(B,
e$B$o$6$o$6$=$s$J$3$H$7$J$/$F$b$h$$5$$,$7$^$9e(B.

e$B$^$?e(B Prime e$B$Ne(B initialize e$B$He(B succ e$B$b$h$jC1=c$K$7$?e(B
(e$BCfN,e(B)
e$B$NJ}$,B.$/$J$k$h$&$G$9!#e(B

e$B$3$A$i$G$9$,e(B, ruby1.8, ruby1.9e$B$I$A$i$GHf3S$7$^$7$?e(B?
1.9e$B$NJ}[email protected]$$$VJQe(B
e$B$o$C$F$$$k$N$G$9$,e(B…

__
---------------------------------------------------->> [email protected](B
e$B7=<ye(B <<—
---------------------------------->> e-mail: [email protected] <<—

#4

e$B$1$$$8$e!w$$$7$D$+$G$9e(B.

In [ruby-dev:30932] the message: “[ruby-dev:30932] Re:
Integer#prime_division e$B$He(B Prime”, on Jun/08 17:48(JST) TOYOFUKU
Chikanobu writes:

e$BK-J!$G$9!#e(B

ps = (2…self) e$B$G$h$$$H$$$&0UL#$G$9$+!)e(B

e$B$G$7$?e(B.

 else
   case prime
   when 1; prime = 2
   when 2; prime = 3
   when 3; prime = 5; step = 2
   end
 end

e$B$&!<$`e(B. e$B$3$C$A$N$[$&$,?tG\Aa$$$G$9$Me(B.
e$B$3$C$A$K$5$;$F$/[email protected]$5$$e(B.

__
---------------------------------------------------->> [email protected](B
e$B7=<ye(B <<—
---------------------------------->> e-mail: [email protected] <<—

#5

e$BK-J!$G$9!#e(B

e$B$1$$$8$e!w$$$7$D$+$G$9e(B.

e$B$*5W$7$V$j$G$9!#e(B

e$B!J<BMQ$K$Oe(B 2,3e$B$He(B e$B!^e(B1(mod 6) e$B$"$?$j$r;H$&$N$,$h$$$G$7$g$&$+!Ke(B

e$B$3$A$i$be(B,
…
e$B$H$J$C$F$$$^$9$N$Ge(B, e$B$o$6$o$6$=$s$J$3$H$7$J$/$F$b$h$$5$$,$7$^$9e(B.

ps = (2…self) e$B$G$h$$$H$$$&0UL#$G$9$+!)e(B
e$B#2$H#3$NG?t$/$i$$$Oe(B
e$B4V0z$$$?J}$,e(B (e$BBg$-$J?te(B).divmod(prime)
e$B$r>/$7$G$b>J$1$F$h$5$=$&$Je(B
e$B5$$,$7$^$9$,!#;d$O<!$N$h$&$J$N$r9M$($F$^$7$?!#e(B

prime = 1
step = nil
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

e$B$^$?e(B Prime e$B$Ne(B initialize e$B$He(B succ e$B$b$h$jC1=c$K$7$?e(B
(e$BCfN,e(B)
e$B$NJ}$,B.$/$J$k$h$&$G$9!#e(B

e$B$3$A$i$G$9$,e(B, ruby1.8, ruby1.9e$B$I$A$i$GHf3S$7$^$7$?e(B? 1.9e$B$NJ}[email protected]$$$VJQe(B
e$B$o$C$F$$$k$N$G$9$,e(B…

e$B$*!"K\[email protected]!#$9$C$+$jJQ$o$C$F$^$9$M!#e(Bruby1.8
e$B$N$r8+$F$^$7$?!#e(B

                    e$BK-J!e(B
#6

e$BK-J!$G$9!#e(B

e$B;d$O<!$N$h$&$J$N$r9M$($F$^$7$?!#e(B

e$B$b$&0l%v=j$"$j$^$7$?!#e(B

break if prime * prime >= value

e$B$N$H$3$m$Oe(B

break if value1 <= prime

e$B$G$h$$$H;W$$$^$9!#e(B

                    e$BK-J!e(B