1+2+...+n的约数(6) - 重体验: 我还可以再快吗？

问题解决的时候，一切都是那么舒爽...
一直以来，写的程序都是为了在限定时间以内运行而努力。
而这次，第一次想把自己的程序速度再进一步。

嗯，回到开始的想法：去除重复运算，用memory换时间
f(n)=n(n+1)/2=n1*n2 (n1=n/2，n2=n+1或者n1=n，n2=(n+1)/2)
因为n，n+1相邻，所以n1与n2之间没有共同的质数约数
n1与n2之间没有共同的质数约数！
也就是说 f(n)的约数个数 = n1的约数个数 × n2的约数个数

而f(n)和f(n+1)都会有个共同的部分 n+1 (或(n+1)/2)
这就是说：我们可以节省这部分重复运算！
这可以节省1/2甚至更多的运算量！

coding如下

代码:

class Divisor
  # primes: [2, 3, 5, 7, ...]
  #attr_accessor :primes, :offset, :memory
  
  def initialize
    @primes = Array.new(1, 2)
    @offset = 3
    @memory = Array.new
  end
  
  def n(num)
    return 1 if (num == 1)
    
    n = 2
    n += 1 while (num_of_divs(n) < num)
    
    return n
  end
  
  # add n if it is a prime
  def add_prime(n)
    sqrt = Math.sqrt(n).to_i    
    @primes.each do |prime|
      break if (prime > sqrt)
      return if (n % prime == 0)
    end
    
    @primes << n
  end
  
  # number of divisors of f(n) = 1 + 2 + ... + n = n(n+1)/2
  def num_of_divs(n)
    n1 = n
    n2 = n +1
    sqrt = Math.sqrt(n2).to_i
    
    # if not added (into primes' list), try to add it,
    if (sqrt >= @offset)
      add_prime(sqrt) 
      @offset += 1  #increase prime offset
    end
    
    # f(n) = n(n+1)/2 could be as multiplication of two numbers, either (n/2) * (n+1) or n * [(n+1)/2]
    if (n1 % 2 == 0)
      n1 /= 2
    else
      n2 /= 2
    end
    
    return num_of_divs_ex(n1) * num_of_divs_ex(n2) 
  end
  
  # number of divisors of n
  def num_of_divs_ex(n)
    return @memory[n] if @memory[n] #return if it is already stored in memory
    
    count = 1
    m = n
    @primes.each do |prime|
      break if (m == 1)
      
      if @memory[m]
        count *= @memory[m]
        @memory[n] = count
        return count
      end
      
      # check whther <prime> is one of divisor of <m>
      tmp = 0
      while (m % prime == 0)
        tmp += 1
        m /= prime
      end
      
      # update <count> if <prime> is one of divisor of <m>
      count *= (tmp + 1) if (tmp > 0)    
    end
    
    count *= 2 if (m != 1)
    @memory[n] = count
    return count
  end
end

start = Time.now
div = Divisor.new
print '->' + div.n(500).to_s + '<-'
final = Time.now
cost =final - start
print 'Cost: ' + cost.to_s

500个约数仅需要0.313s，速度提高了将近3倍...