From: keiju@... (=?ISO-2022-JP?B?GyRCQFBETTc9PHkbKEI=?=)
Date: 2007-06-08T17:21:56+09:00
Subject: [ruby-dev:30931] Re: Integer#prime_division と Prime

けいじゅ＠いしつかです.

In [ruby-dev:30920] the message: "[ruby-dev:30920]
Integer#prime_division と Prime", on Jun/07 18:11(JST) TOYOFUKU
Chikanobu writes:

>  豊福です。

お久しぶりでございます.

>  ((2**17-1)**2).prime_division に比べて ((2**19-1)**2).prime_division
>の時間が異様にかかるので調べたところ Integer#prime_division
>の中の
>  ps = Prime.new
>から素数列を生成するのにコストがかかっていて、より単純な
>  ps = (2..n)
>を使う方が速くなるようです。

なるほど, すでに割りきれるだけ割りきっているので, わざわざ素数列を用い
る必要はないわけですね.

>（実用には 2,3と ±1(mod 6) あたりを使うのがよいでしょうか）

こちらも, 

    for prime in ps
      count = 0
      while (value1, mod = value.divmod(prime)
	     mod) == 0
	value = value1
	count += 1
      end
      if count != 0

となっていますので, わざわざそんなことしなくてもよい気がします.


>  また Prime の initialize と succ もより単純にした
(中略)
>の方が速くなるようです。

こちらですが, ruby1.8, ruby1.9どちらで比較しました? 1.9の方はだいぶ変
わっているのですが...


__
---------------------------------------------------->> 石塚 圭樹 <<---
---------------------------------->> e-mail: keiju@ishitsuka.com <<---