モジュール詳細：互いに素チェック

ペアをチェック！

このモジュールは2つのボタン、表示された2つの数字、3つのステージライトで構成されている。これらのボタンには、それぞれ「Coprime(互いに素)」と「Not Coprime(互いに素ではない)」と表示される。

モジュールを解除するには、数字のペアに対応する1つのボタンを正確に3回押す必要がある。数字のペアが互いに素である場合、「Coprime」を押す必要がある。それ以外の場合、数字のペアが互いに素ではない場合、「Not Coprime」を押す必要がある。間違ったボタンを押すとミスが記録され、新しい数字が生成される。

数字のペアが互いに素であるかどうかを判断するには、これら2つの数値の間で素因数分解を行う。数値のペアに対して共通する約数がない場合、数字のペアは互いに素である。

数字を素因数分解するには、元の数字をそれよりも小さい素数で除算してみる。結果に余りが出る場合、これ以上割り切れなくなるまで別の素数で除算してみる。それ以外の場合はその素因数を記録し、商を新しい元の数字としてこの手順を繰り返す。割り切れなくなったら、その時点で記録されている数字がその数字の素因数分解の結果となる。

素因数分解の例は以下に記されている。

素因数分解例
966	素因数分解前
2 × 483	966は2で除算できる
2 × 3 × 161	483は2では除算できないが3で除算できる
2 × 3 × 7 × 23	161は2，3，5では除算できないが7で除算できる
	23は素数である。素因数分解が終了した。

748	素因数分解前
2 × 374	748は2で除算できる
2 × 2 × 187	374は2で除算できる
2 × 2 × 11 × 17	187は2，3，5，7では除算できないが11では除算できる
	17は素数である。素因数分解が終了した。