查看完整版本: 也来讨论Projecteuler的分解质因数题目～

也来讨论Projecteuler的分解质因数题目～

[code]class Projecteuler::Problem003
  #The prime factors of 13195 are 5, 7, 13 and 29.

  #What is the largest prime factor of the number 600851475143 ?
  
  #把一个自然数化成N个质数的乘积（分解质因数）。e.g. 100=2*2*5*5，最大质因数为5。
  #这里考虑了算法优化：
  #制作一本字典，经过整本字典的过滤，分解下来还不被字典包含，也往往就是最大质因数了。
  attr_reader :largest_pf,:pf_of_the_number
  
  def initialize
    @@ori_number = 595959595959595959595959   #是不是更有挑战性^^#600851475143

    pf_dic = [2]  #定义质数字典
    @@dic_limit = 9999  #字典里最大的质数不超过此值。
    @largest_pf = nil
    @pf_of_the_number = []
   
    #找出3到dic_limit之间所有的质数做成字典。2以后的质数都是奇数，可以2步一跳
    3.step(@@dic_limit,2) do |x|  
      found = false
      for i in 2...x**0.5  #从2起循环查找能除尽x的数，找到证明x不是质数，跳出循环。考虑x的平方根以内的数就行了。
        if x % i == 0
          found = true
          break
        end
      end
      pf_dic << x unless found
    end
   
    the_number = @@ori_number
    #用字典过滤the_number
    pf_dic.sort.each do |pf|
      while the_number % pf == 0 and the_number != pf
        the_number /= pf
        @pf_of_the_number << pf
      end
    end
   
    #经字典过滤后，继续找dic_limit之外能除尽the_number的数，找到说明字典设得不够大，没找到即证明the_number为最大质数。
    found = false
    for i in (@@dic_limit+1)...the_number**0.5
      if the_number % i == 0
        found = true
        break
      end
    end
   
    unless found  #else should augment the dic_limit
      @largest_pf = the_number
      @pf_of_the_number << @largest_pf
      puts "#{@@ori_number} = #{@pf_of_the_number.join("*")}"
    end
   
  end
  
end[/code]程序的输出
>595959595959595959595959 = 3*7*13*37*59*73*101*137*9901*99990001
做了一些大数字的测试，最大质因数若是超过12位，判断其是不是质数的部分就慢了。。

[[i] 本帖最后由 595959 于 2008-4-8 17:50 编辑 [/i]]

为什么让字典里的质数不超过9999?

额，注释表达的不好，@@dic_limit用做字典的上限，字典里的质数不超过@@dic_limit。
大了二层循环会影响些速度，9999运行这个程序花费0.4秒，99999就要9秒了～

这是我当初的解,稍微优化了一点[code]  def g(x)
    return 2 if x % 2 == 0
    sqar = (x ** 0.5).to_i
    3.step(sqar , 2){|i| return i if x % i == 0}
    return x
  end

  def f(x)
    div = []
    y = g(x)
    until x == y
      div << y
      x /= y
      y = g(x)
    end
    div << y
    return div
  end

  t0 = Time.now
  p f(595959595959595959595959)
  p Time.now - t0[/code]

[quote]原帖由 [i]595959[/i] 于 2008-4-8 18:17 发表 [url=http://www.ruby-lang.org.cn/forums/redirect.php?goto=findpost&pid=13857&ptid=4175][img]http://www.ruby-lang.org.cn/forums/images/common/back.gif[/img][/url]
额，注释表达的不好，@@dic_limit用做字典的上限，字典里的质数不超过@@dic_limit。
大了二层循环会影响些速度，9999运行这个程序花费0.4秒，99999就要9秒了～ [/quote]

这样的话得根据要分解的数的大小来回变@@dic_limit的值?不是特方便吧

上限9999为了保证程序执行时间。。
bbschat兄的(x**0.5).to_i很关键啊！

[[i] 本帖最后由 595959 于 2008-4-8 19:51 编辑 [/i]]

好像(x**0.5)没必要to_i了，参考[code]0.upto(10**0.5) {|i| puts i }
#=>0
1
2
3[/code]

upto 没必要，step 就有必要了，xavier 可以试下，原因未知。

ps： 个人猜想也许是因为 upto 的步长固定是1。 而 step 步长不固定，且允许使用小数的原因。
所以Ruby对 step 的第一个参数不会自动取整。

[[i] 本帖最后由 bbschat 于 2008-4-9 18:25 编辑 [/i]]

确实是这样的，以前到真没怎么用过step
step是Numeric的实例方法，所以所有数字都能用
见：[code]n= Numeric.new
puts true if n.respond_to?("step")[/code]

帖子不错2

楼主辛苦了，多谢你的帖子，继续努力．

















[img]http://www.chinaser.net/images/default/sigline.gif[/img]
[color=#000066]我的座右铭：Study English in order to apply it wow gold.Language is for the [/color][url=http://www.eq2goldplat.com][color=#000066]wow gold[/color][/url][color=#000066] exchange of ideas, for communication.A great man [/color][url=http://www.ppwowgold.com][color=#000066]wow gold[/color][/url][color=#000066] once said it is necessary to dill [/color][url=http://www.hhwowgold.com][color=#000066]wow gold[/color][/url][color=#000066] as much as possible, and [/color] [url=http://www.wowgoldwarcraft.com][color=#000066]wow gold[/color][/url][color=#000066] the more you apply it in real situations, the more natural it will become.一位伟人曾说，反复练是非常必要的，你越多地将所学到的东西运用到实际生活中，他们就变得越自然。这就是我学习英语的技巧，我现在都可以跟老外直接对话了。[/color]