のてすきあ − 完全独習非プログラマー −

Haskell で Project Euler を解く素人遊び

2020-10-11から1日間の記事一覧

Problem 72

分母が1,000,000以下の既約分数は全部でいくつあるか。 問題は を求めることと同義である。ここまで重い計算を避けるために、φ関数を直接計算することは避けてきたが、この問題ではさすがにそうもいかない。連想リストで効率化をはかりつつ、計算は真っ向勝…

Problem 71

分母が1,000,000までの既約分数を小さい順に並べた時に、3/7の1つ前に来る分数(3/7より小さく、3/7に最も近い数)はなにか まず思いつくのは、全ての分数を列挙してsortして…というナイーブな手法だが、恐らくその方法では時間が掛かり過ぎる。もう少し論理…