Keep Hacking :)

Life is complex, it has both real and imaginary parts.

Project Euler 124的解答

題目是這樣說的，有一個函數叫做rad，它是去運算一個整數的所有的質因數的乘積。題目要問的就是請我們對1~100000中的數字用rad的大小做排序(如果rad一樣大，就再用數字的大小去做排序)之後，問排序後第10000的數字是誰？

妳被迷惑了嗎？

其實這題我們並不用去真的對數字去做排序，甚至也不用有個大質數表來做質因數分解:p

我的想法就是去推廣 Sieve of Eratosthenes，但是不是將數字給刪除，反倒是將它建成一個表，去記錄她被哪些質數給整除過，然後在用rad的數字去建一個表，將rad值一樣的數字存入，最後在去算第10000的數字是誰就好了:D

附上程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#!/usr/bin/env ruby

limit, target = 100_000, 10_000
rad = Hash.new { |h, k| h[k] = 1 }
cache = Hash.new { |h, k| h[k] = [] }

(2 .. limit).each do |x|
  if rad[x] == 1
    x.step(limit, x) { |y| rad[y] *= x }
  end
  cache[rad[x]] << x
end

cache.each_value do |v|
  if target <= v.size
    puts v[target - 2] #ignore 1 
    break
  end
  target -= v.size
end

這樣子就可以很快的算出答案了:D

Comments