Problem3

13195 の素因数は 5、7、13、29 である。

600851475143 の素因数のうち最大のものを求めよ。

最初に書いたのがこれ。「素数列を出してから計算」したら9桁くらいから計算時間が急激に伸び、結局12時間かかっても終わらなかった。しかも最大素因数求めてないことに途中で気づいた。
Haskell

main=print maxFactor
target=600851475143
maxFactor=maxim [x|x<-(findNewPrime 2 []),target `mod` x==0]

maxim::[Integer]->Integer
maxim []=0
maxim (x:xs)=max x $ maxim xs

findNewPrime::Integer->[Integer]->[Integer]
findNewPrime 2 []=findNewPrime 3 [2]
findNewPrime current xs=
  if (isNewPrime current xs) then 
     if (current ^ 2 < target) then findNewPrime (current+2) (current:xs)
     else (current:xs)
  else findNewPrime (current+2) xs

isNewPrime::Integer->[Integer]->Bool
isNewPrime n []=True
isNewPrime n (x:xs)=if (n `mod` x==0) then False else (isNewPrime n xs)

ハチロクskypeに聞きに行ったら「素直に順に割れ」ということだったので、書き直してみたらこうなった。

main=print $ test  600851475143 2
test tg n
  |n*n > tg      = [tg]
  |(mod tg n)==0 = concat [test n 2, test (div tg n) 2]
  |otherwise     = test tg (n+1)

[71,839,1471,6857]

やってるのは最大素因数というか素因数分解だけど、一瞬で出た。

• アルゴリズムこわい。
• (haskell関係ないけど)gdbの使い方習った。
• ガードの使い方覚えた。
• ハイレベルの人々に色々教えてもらえて嬉しかった。みんな一瞬で答え出してたw

夜を徹していろいろ考えてくれたid:nishiohirokazu,id:suztomo,id:hogelogほかハチロクskype住人のみなさんに感謝！

一日一チベットリンク

青海チベット鉄道紀行

2006年08月26日

青藏鉄道紀行

早く乗らなきゃチベット鉄道
　チベット鉄道が開通した。06年7月1日、中国各地からチベットのラサをめざして一番列車が出 発した。これはなんとしても早く乗らにゃなるまい。できれば7月中に行きたいものだ。実は４月 ころから、仕事でよくチベットにでかける北京の友人に切符を買ってくれるように頼んでおいた が、彼いわく「だいじょうぶ。そんなにたくさんの人が行く所じゃないから問題ありません」そうか なと思ったが、7月1日からの営業試運転のニュースが中国中に大々的に流れると、チベット人 気は一気にヒートアップ。切符を頼んである友人はヨーロッパに出張中で連絡とれず、別の知り 合いに電話を入れると、旅行社に頼んでもほとんどだめ、ダフ屋が買い占めた、ニセ切符が出 回っている、今週からラサ行き切符はしばらく販売しないそうだ。などいい情報はなかった。