# Integer#prime\_division $B$H(B Prime

**URL:** <https://www.ruby-forum.com/t/integer-prime-division-b-h-b-prime/106194>\
**Category:** Development\
**Created:** [June 7, 2007, 11:12am UTC](https://www.ruby-forum.com/t/integer-prime-division-b-h-b-prime/106194 "2007-06-07T11:12:48Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![TOYOFUKU\_Chikanobu](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/5daacb/32.png) [@TOYOFUKU\_Chikanobu](https://www.ruby-forum.com/u/TOYOFUKU_Chikanobu)\
**Post date:** [June 7, 2007, 11:12am UTC](https://www.ruby-forum.com/t/integer-prime-division-b-h-b-prime/106194/1 "2007-06-07T11:12:48Z")

</div>

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

((2\*\*17-1)**2).prime\_division e$B$KHf$Y$Fe(B  
((2**19-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  
e$B$+$iAG?tNs$r@8@.$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
                    removed_email_address@domain.invalid
```

---

<div class="post-metadata">

**Author:** ![TOYOFUKU\_Chikanobu](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/5daacb/32.png) [@TOYOFUKU\_Chikanobu](https://www.ruby-forum.com/u/TOYOFUKU_Chikanobu)\
**Post date:** [June 7, 2007, 11:18am UTC](https://www.ruby-forum.com/t/integer-prime-division-b-h-b-prime/106194/2 "2007-06-07T11:18:49Z")

</div>

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
                    removed_email_address@domain.invalid
```

---

<div class="post-metadata">

**Author:** ![TOYOFUKU\_Chikanobu](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/5daacb/32.png) [@TOYOFUKU\_Chikanobu](https://www.ruby-forum.com/u/TOYOFUKU_Chikanobu)\
**Post date:** [June 8, 2007, 10:22am UTC](https://www.ruby-forum.com/t/integer-prime-division-b-h-b-prime/106194/3 "2007-06-08T10:22:43Z")

</div>

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 ((2**19-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  
> e$B$+$iAG?tNs$r@8@.$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, e$B$9$G$K3d$j$-$l$k$@$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}$O$@$$$VJQe(B  
e$B$o$C$F$$$k$N$G$9$,e(B…

\_\_  
----------------------------------------------------\>\> e$B@PDMe(B  
e$B7=\<ye(B \<\<—  
----------------------------------\>\> e-mail: removed\_email\_address@domain.invalid \<\<—

---

<div class="post-metadata">

**Author:** ![TOYOFUKU\_Chikanobu](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/5daacb/32.png) [@TOYOFUKU\_Chikanobu](https://www.ruby-forum.com/u/TOYOFUKU_Chikanobu)\
**Post date:** [June 8, 2007, 11:50am UTC](https://www.ruby-forum.com/t/integer-prime-division-b-h-b-prime/106194/4 "2007-06-08T11:50:51Z")

</div>

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$/$@$5$$e(B.

\_\_  
----------------------------------------------------\>\> e$B@PDMe(B  
e$B7=\<ye(B \<\<—  
----------------------------------\>\> e-mail: removed\_email\_address@domain.invalid \<\<—

---

<div class="post-metadata">

**Author:** ![TOYOFUKU\_Chikanobu](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/5daacb/32.png) [@TOYOFUKU\_Chikanobu](https://www.ruby-forum.com/u/TOYOFUKU_Chikanobu)\
**Post date:** [June 8, 2007, 10:49am UTC](https://www.ruby-forum.com/t/integer-prime-division-b-h-b-prime/106194/5 "2007-06-08T10:49:47Z")

</div>

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}$O$@$$$VJQe(B  
> e$B$o$C$F$$$k$N$G$9$,e(B…

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

```
                    e$BK-J!e(B
```

---

<div class="post-metadata">

**Author:** ![TOYOFUKU\_Chikanobu](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/5daacb/32.png) [@TOYOFUKU\_Chikanobu](https://www.ruby-forum.com/u/TOYOFUKU_Chikanobu)\
**Post date:** [June 8, 2007, 8:42pm UTC](https://www.ruby-forum.com/t/integer-prime-division-b-h-b-prime/106194/6 "2007-06-08T20:42:01Z")

</div>

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
```