分析下题目吧，很明显，f(n)的约数个数不是随着n的递增而递增的，解的过程是从n=1求起，递增，直到f(n)有超过500个约数，返回n值
f(n)的约数个数怎么求呢？
一个for loop, 从1到f(n)，依次检查起是否为f(n)的约数...
又是很明显的，用这种方法的话可以拿块豆腐把自己撞死了...
也许，这种方法需要若干年才能完成计算吧...
质数，质数...
假设f(n) = (a^i) * (b^j) * (c^k) * ... (a, b, c为质数)
那么f(n)的约数共有(i+1) * (j+1) * (k+1) *...个
提高运算速度最常用的方法是避免重复计算，而最常用的手法则是用memory换时间...
要保存什么内容以提高运算速度呢？
1. 质数是不能缺的，[2, 3, 5, 7, 11, ...]
2. 一个自然数n分解成质数所形成的数组[i, j , k, ...]
例如n = 15 = 3*5可以用[0,1,1]表示，即 n = (2^0) * (3^1) * (5^1)
这样计算2n时我们发现2n=2*n, 于是2n用[1] + [0, 1, 1] = [1, 1, 1]表示
让我们来coding吧。(代码见评论)
f(n)的约数个数怎么求呢？
一个for loop, 从1到f(n)，依次检查起是否为f(n)的约数...
又是很明显的，用这种方法的话可以拿块豆腐把自己撞死了...
也许，这种方法需要若干年才能完成计算吧...
质数，质数...
假设f(n) = (a^i) * (b^j) * (c^k) * ... (a, b, c为质数)
那么f(n)的约数共有(i+1) * (j+1) * (k+1) *...个
提高运算速度最常用的方法是避免重复计算，而最常用的手法则是用memory换时间...
要保存什么内容以提高运算速度呢？
1. 质数是不能缺的，[2, 3, 5, 7, 11, ...]
2. 一个自然数n分解成质数所形成的数组[i, j , k, ...]
例如n = 15 = 3*5可以用[0,1,1]表示，即 n = (2^0) * (3^1) * (5^1)
这样计算2n时我们发现2n=2*n, 于是2n用[1] + [0, 1, 1] = [1, 1, 1]表示
让我们来coding吧。(代码见评论)
然而，想象是美好的，结局是残酷的。
测试一下，发现50个约数需要0.922s，100个约数14.7s，500个约数....不敢想象了...
那个6s的确实够强大....
测试一下，发现50个约数需要0.922s，100个约数14.7s，500个约数....不敢想象了...
那个6s的确实够强大....
@Sept. 12, 2008
ReplyDeleteclass Divisor
# prime_list: [2, 3, 5, 7, ...]
# prime_id: [nil, nil, 0, 1, nil, 2]
# div_list:[nil, nil, [1], [0, 1], [2, 0], [0, 0, 1], ...]
attr_accessor :prime_list, :prime_id, :div_list
def initialize
@prime_list = Array.new
@prime_id = Array.new
@div_list = Array.new
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)
final = (n + 1) * n /2
if (n > 1)
cur = (n - 1) * n / 2 + 1
while (cur < final)
num_of_divs_ex(cur, false)
cur += 1
end
end
return num_of_divs_ex(final, true)
end
# number of divisors of f(n) = 1 + 2 + ... + n = n(n+1)/2
def num_of_divs_ex(n, need_ret)
sqrt = Math.sqrt(n).to_i
numOfPrime = @prime_list.size
# Check whether given number is a prime
first_prime = 0
is_prime = true
# already some primes
if (numOfPrime > 0)
@prime_list.each do |prime|
break if (prime > sqrt)
# given number could be divided by some prime
if (n % prime == 0)
is_prime = false
first_prime = prime
break
end
end
end
#generate its divisors' list
divs = nil
if (is_prime)
divs = Array.new(numOfPrime, 0)
divs << 1
@prime_list << n
@prime_id[n] = numOfPrime
else
saved_div = (n / first_prime).to_i
divs = Array.new(@div_list[saved_div]) # copy saved divs
prime_pos = @prime_id[first_prime]
divs[prime_pos] += 1
end
@div_list[n] = divs
return 0 if not need_ret
count = 1
divs.each do |part|
count *= (part + 1) if (part > 0)
end
return count
end
end
start = Time.now
div = Divisor.new
print '->' + div.n(100).to_s + '<-'
final = Time.now
cost =final - start
print 'Cost: ' + cost.to_s