Project Euler 最初の10問を分析する

Project Euler が提供している問題を解くための考え方を紹介してきました。最初の10問を紹介できたので、その10問について、どのような知識があれば解くことができるのか分析しました。

問題を解いた人数

以下は、問題別の解いた人数です（2022年8月14日時点）。

Project Euler では、アカウント作成直後から、すべての問題に挑戦することができるため、問1から問10から順番に解く必要はありません。そのため、問題の取り組みやすさは、解いた人数に現れてきます。

2022年8月14日時点で、1問でも解いた人は、1037913人いました（この1問は、問題1とは限りません）。一方、10問解いた人は、329332人で、1問でも解いた人との比率は、31.73%でした。アカウント登録して、1問解いても、10問解く人は3分の1以下になるようです。

わたしは、C でプログラミングをしましたが、以下は、他の手続き型のプログラミング言語でも同じようなことが当てはまります。

以下の文法知識を前提として、各問題を解くために、追加でどのような文法知識が必要か洗い出しました。改善版、別解で利用した文法要素も含みます。

問題No	問題を解くために必要な追加の C言語の文法要素
1	論理OR演算子（`\|\|`）代入演算子（`+=`）
2	代入演算子（`+=`）
3	unsignd long long int 型 typedef による型定義マクロ定数の定義 scanf による入力
4	なし
5	unsignd long long int 型 typedef による型定義 break 文代入演算子（`*=`）関数の再帰呼び出し
6	代入演算子（`+=`）
7	limits.h（MAX_INT を参照）マクロ定数の定義 break 文配列代入演算子（`+=`）論理AND演算子（`&&`）
8	unsignd long long int 型 typedef による型定義文字列文字列の連結配列数字の文字コード（文字としての数字から数への変換）型のキャスト continue 文
9	マクロ定数の定義
10	unsignd long long int 型 typedef による型定義マクロ定数の定義 break 文代入演算子（`+=`）型のキャスト配列マクロ関数の定義

わたしは、プログラムをなるべく平易に書くように努めていて、使う文法要素も絞っていたつもりでしたが、細かく調べてみると、多くの文法要素を使っていました。

そのプログラミング言語が定めている文法を可能な限り利用してプログラムを記述することと、よく知られている文法を使って平易に書くことのバランスを考えて、書き方を採用しているつもりです。これは次回の話題とさせてください。

数学的な知識も洗い出してみましょう。自然数の概念と四則演算は前提知識とします。

問題No	問題を解くために必要な数学の知識
1	倍数の考え方数列の和の公式（1から$N$の和）
2	漸化式の考え方フィボナッチ数列の定義合同式の考え方（考察で利用）
3	素数の定義素因数分解
4	10進法の記法のしくみ（位取り記数法）倍数の考え方
5	倍数の考え方素数の定義最大公約数ユークリッドの互除法
6	数列の和の公式（1から$N$の和と2乗の公式）
7	素数の定義
8	なし（掛け算の知識があれば解ける）
9	ピタゴラス数の性質
10	素数の定義エラトステネスの篩

高校数学の範囲の知識は必要ですが、多くは高校1年で履修する範囲です。Project Euler は数学的な要素が強い問題を提供していますが、数学の知識をそれほど必要としない問題もあることが分かります。

Project Euler の最初の10問について、以下を整理しました。

C言語と数学について、どれくらいの知識があれば、プログラミングが書けるようになるのか、別の記事で考察します。