Project Euler (Problem 3〜10) - ブートストラッピングでコンパイラを作る日記

8問ときました。

Problem 3

600851475143の最大素因数を求めよ

「素因数分解せよ」ではなく「最大素因数だけ求めよ」ですから素数のテーブルは作りたくないので、反復により求める事を考えます。
整数Nを素因数分解してみると
$N = p_1^{m_1}p_2^{m_2}\cdots p_n^{m_n}\qquad(p_1\le p_2\le\cdots p_n)$
となりますが、これの最小の素数を全部取り除けば、以下の右辺の最大素因数をもとめることと同じです。
$\frac{N}{p_1^{m_1}} = p_2^{m_2}\cdots p_n^{m_n}$
これをどんどん繰り返していって、最後に残ったものが求める最大素数です。
で、ある素数pを取り去った後次に取り去る素数qですが、これはp+2,p+4,..と試して言って最初に割り切れた奴になります。なぜならば、qより小さい素数はすでに全部なくなっているからです。従ってコードは次の様になります。

n = 600851475143
k = 3
while n > k do
    while n % k == 0 do
        n /= k
    end
    k += 2
end
puts k

Problem 4

３桁の整数の積からなる最大の回文数を求めよ

3桁の整数の積は5 or 6桁ですからまず6桁の時を調べます。
3桁の整数の積を列挙するというのも手ですが、数え上げの基本は「条件の厳しい物を良く調べる」ですので、回文数の方を先に調べるのが筋です。最大の物を求めるので、大きい方から順に列挙すると

999999, 998899, 997799, 996699, 995599, 994499, 993399, ..., 102201, 101101, 100001

となりますので、綺麗に下降している上3桁に注目すると良いでしょう。これをkとおきます。
kの100,10,1の位はそれぞれ
$a = \lfloor k/100 \rfloor \\b = \lfloor k/10 \rfloor - \lfloor k/100 \rfloor 10 \\c = k - \lfloor k/10 \rfloor$
となるので、これから回文数の一般項が作れます。
$a10^5+b10^4+c10^3+c10^2+b10+a\\= 11(100k-90\lfloor k/10 \rfloor-9\lfloor k/100 \rfloor)$
6桁の回文数は11の倍数である事が分かります。一般的には偶数桁の回文数はかならず11の倍数です。
100k-...の部分ををAとおいて、2つの整数を11pとqとすると、桁数の制限から
$pq = A\\10^2 \le 11p < 10^3 \\10^2 \le q < 10^3 \\10^5 \le 11A < 10^6$
となるので、以下を満たせばOKです。
$\frac{A}{10^3} < p \le \frac{10^3}{11}$
以上より解答は以下のようになります。

999.downto(100) do |k|
    a = 100*k-90*(k/10)-9*(k/100)
    ((a+999)/1000..90).each do |p|
        if a % p == 0
            puts "#{11*a} = #{11*p} * #{a/p}"
            exit
        end
    end
end

Problem 5

1 から 20 の整数全てで割り切れる最小の整数を求めよ

つまり最小公倍数の事だから必要な素数を列挙すると

2は16=2^4なので最大4つ
3は9=3^2なので最大2つ
5,7,11,13,17,19は2乗すると20を超えるから最大1つ

という訳で

2^4*3^2*5*7*11*13*17*19

が答え

Problem 6

(1+2+...+100)^2-1^2+2^2+3^2+...+100^2を求めよ

和の公式を使って
$\left( \sum_{0< k\le n}k \right)^2 - \sum_{0< k\le n}k^2 \\= \frac{1}{4}n^2(n+1)^2-\frac{1}{6}n(n+1)(2n+1) \\\frac{1}{12}n(n-1)(n+1)(3n+2)$
となるのでn=100を代入して終わり。

Problem 7

10001番目の素数を求めよ

エラトステネスのふるいで良いわけですが、ふるいのサイズを決めなければなりません。こういうときは素数定理が役に立ちます。
今回は素数の値の上限を調べればよいので、以下の式を使います。
n番目の素数をp(n)とするとnが6以上の時は
$p(n) < n(\ln n + \ln \ln n)$
で抑えられます。
またnが20以上の時は
$p(n) < n(\ln n + \ln \ln n - \frac{1}{2})$
で抑えられます。

include Math
n = 10001
N = ( n * (log(n) + log(log(n)) - 1/2) ).floor
sieve = []
count = 0
2.upto(N) do |i|
    next if sieve[i]
    if (count += 1) == n then
        puts i;
        exit
    end
    (2*i).step(N, i) {|p| sieve[p] = true }
end

実行時間は0.15秒くらいだったのでこれで良しとします。
素数定理は計算量を推定する上でも役に立つので是非覚えておくと良いかと思います。

Problem 8

これはおもしろくないので省略

Problem 9

a < b < c かつ a^2+b^2=c^2 かつ a+b+c=1000 を満たす整数a,b,cを求め、abcを答えよ

1文字消去できるのでこれは高校１年くらいで学ぶ2元2次不定方程式の問題。現役高校生ならすぐできるでしょう。
まずはcを消去して定石通り因数分解します。
$a^2+b^2 = (1000-a-b)^2 \\\leftrightarrow (1000-a)(1000-b) = 500000$
今0 < a < bだから1000-a > 1000-bに注意すると
$707 < 1000-a < 1000 \qquad (\sqrt{5000} = \frac{1000\sqrt{2}}{2} = \frac{1414.2...}{2} 707.\cdots)$
が必要です。この範囲での500000の約数は800しか存在しませんからa=200。残りは自動的に出ます。

Problem 10

2000,000以下の素数の和を求めよ

ふつうにエラトステネスのふるいでやります。

N = 2000_000
sieve = []
sum = 0
2.upto(N) do |i|
    next if sieve[i]
    sum += i
    (2*i).step(N, i) {|p| sieve[p] = true }
end
puts sum

nineties% time ruby problem10.rb
142913828922
ruby problem10.rb  3.92s user 0.04s system 99% cpu 3.968 total

よくある高速化としては偶数を最初から取り除いておくという手があります。

N = 2000_000
sieve = []
sum = 2
3.step(N,2) do |i|
    next if sieve[i/2]
    sum += i
    (3*i).step(N, 2*i) {|p| sieve[p/2] = true }
end
puts sum

nineties% time ruby problem10.rb
142913828922
ruby problem10.rb  2.44s user 0.03s system 99% cpu 2.475 total

1.5倍くらい速くなりました。