Problem 3

調子に乗って3問目．このテンションは絶対続かない．
素因数分解は面倒ですが，まぁ候補となり得る素数リストをつくって上から順に割っていくという流れで実装してました．

from math import sqrt
def es(n):
    n /= 2
    chk = [True for i in xrange(n)]
    for i in xrange(n):
        if chk[i]:
            p = i * 2 + 3
            for j in xrange(i+p,n,p):
                chk[j] = False
    primes = []
    for i in xrange(n-1,0,-1):
        if chk[i]:
            primes.append(i * 2 + 3)
    primes.append(2)
    return primes

k = 600851475143
candidates = es(int(sqrt(k)))
for i in candidates:
    if not k % i:
        print i
        break

思ったより長い…．もっと削りたい…．esはエラトステネスの篩を行う関数です．Eratosthenesの頭と最後を取って…．分かりづらいか．平方根までひたすら割り算して素数かどうかという判定をさせるだと短く書ける．ただそれだと遅い．generatorで素数を生成させた方が良かったかも？（短くかつ速いという意味で）ただgeneratorの使い方が今一わかってないんだよなぁ．丁度いいから明日はそこからやろう！
一応素数が大きい順に並べられるようにしています．最初はsort(reverse=True)でも良いかなぁと思いましたが，追加させる順番を逆順にすれば良いだけの話なのでそっちにしました．
でcandidates（候補リスト）は値の平方根までの素数のリストなのでes(int(sqrt(k))となります．あとは上から順に候補の素数を試して割り切れたら探すのをやめます．