1+2+...+n的约数(3) - 再试: 100个约数1.578s， 150个约数67.7s！！

再试: 100个约数1.578s， 150个约数67.7s！！

计划失败，怎么办呢，还是先分析下问题吧...
1. Array的读写吃了太多的时间
2. 太多没必要的计算...

没必要的计算？对，没必要的计算！
1. f(n-1) ~ f(n)之间的值的约数求解浪费了太多运算量
2. f(n) = n(n+1)/2，其实，我们是可以分成n*[(n+1)/2]或者(n/2)*(n+1)算的，把f(n)分成2部分的积，然后分别求解
例如f(8) = 8*9/2 = 4*9 = (2^2) * (3^2)，即[2, 0] + [0, 2] = [2, 2]

结论?
1. 去除f(n-1) ~ f(n)之间的运算量，改回普通计算方式
2. 把f(n)分成2部分求解

代码见评论。

如前所料，速度果然大大提高，然而，与设想的却差了一大截:
50个约数需要0.437s，100个约数1.578s，150个约数67.7s！！ 500个约数....依旧不敢想象...

---------------------------------

class Divisor
  # prime_list: [2, 3, 5, 7, ...]
  attr_accessor :primes
  
  def initialize
    @primes = Array.new(1, 2)
  end
  
  def n(num)
    return 1 if (num == 1)
    
    n = 2
    n += 1 while num_of_divs(n) < num
    
    return n
  end
  
  # number of divisors of f(n) = 1 + 2 + ... + n = n(n+1)/2
  def num_of_divs(n)
    if (n > 1)
      cur = (n - 1) * n / 2 + 1      
      final = (n + 1) * n /2
      while (cur < final)
        add_prime(cur)
        cur += 1
      end
    end
    
    return num_of_divs_ex(n)
  end
  
  def add_prime(n)
    sqrt = Math.sqrt(n).to_i
    
    # already some primes
    if (not @primes.empty?)
      @primes.each do |prime|
        break if (prime > sqrt)
        return if (n % prime == 0)
      end
    end
    
    @primes << n
  end
  
  # number of divisors of f(n) = 1 + 2 + ... + n = n(n+1)/2
  def num_of_divs_ex(n)
    n1 = n
    n2 = n +1
    sqrt = Math.sqrt(n2).to_i
    
    if (n1 % 2 == 0)
      n1 /= 2
    else
      n2 /= 2
    end

    count = 1
    if (not @primes.empty?)
      @primes.each do |prime|
        break if (n1 == 1 && n2 == 1)
        if (prime > sqrt)
          count *= 2 if (not n1 == 1)
          count *= 2 if (not n2 == 1)
          break
        end
        
        tmp = 0
        while (n1 % prime == 0)
          tmp += 1
          n1 /= prime
        end
        while (n2 % prime == 0)
          tmp += 1
          n2 /= prime
        end
        
        count *= (tmp + 1) if (tmp > 0)
      end
    end
    return count
  end
end

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