Scratch で素因数分解と約数♪
-
0
-
-
素数とは、1と、その数でしか割ることができない数のことを言います。その素数は、今日のセキュリティ技術を支える根幹でもあります。
今回は、素数自体が題材ではなく、素因数分解と約数についてです。
約数は、その数で割れる数であります。その単純な判定方法は、その数を１から変えていき、割り切れる数を列挙する方法です。
たとえば、10 という数の約数を求める場合、10 ÷ 1 = 10 , 10 ÷ 2 = 5 , 10 ÷ 3 = 3.333・・・ , 10 ÷ 9 = 1.111・・・ , 10 ÷ 10 = 1 という感じです。
ですが、その数が大きな数になると、とてもそのような計算で求めることは不可能になります。
素因数分解は、その数を素数の割り算に分解することです。一般的に、素因数分解は、その数のルート(平方根)以下の数で割ることで求めることができます。
その数の約数は、その数のルート(平方根)以下の数とその数を平方根以下の数で割った数のペアを求めることにより、その数の約数を求めることができます。
例えば、10 の約数を求める場合、10 の平方根は、3.15227766・・・となり、3 までの数で求めることになります。
1 は、10 で割り切れるので、その掛ける数 10 とのペア
2 は、10 で割り切れるので、その掛ける数 5 とのペア
3 は、10 で割り切れないの、約数ではない
単純な判定方法だと、10回繰り返し計算しないといけないですが、素因数分解を用いた方法だと、3回繰り返し計算すれば、求めることができます。
※ 素因数分解については、Wikipedia をご参照ください。
今回は、単純な判定の方法(ねこさん)と素因数分解を用いた方法(さかなさん)の二種類の方法で約数を求めるプログラムを作成しました。その数が大きい場合は、素因数分解を用いた方法が早く列挙するのが見えてわかると思います。
Scratch サイトに、公開をしましたので、こちらをごらんください。
LINE＠お友だち募集中です(≧▽≦)
2時間無料の登録特典もお見逃しなく(^_-)-☆
☆.｡.:*･ﾟ☆.｡.:*･ﾟ☆.｡.:*･ﾟ☆.｡.:*･ﾟ☆.｡.:*･ﾟ☆.｡.:*･ﾟ☆.｡.:*･ﾟ☆.｡.:*･ﾟ☆.｡.:*･ﾟ☆.｡.:*･ﾟ☆.｡.:*･ﾟ☆.｡.:*･ﾟ☆.｡.:*･ﾟ☆.｡.:*･ﾟ
プログラミング教室 受講生
電子工作教室 体験受講
募集中です(*^-^*)
子どもプログラミング教室をご参照ください！！！
電子工作教室は、体験受講募集中です。
土曜、日曜日の午前中に行っております（要予約）
ご関心をお持ちの方は、ぜひお問い合わせを(#^^#)
☆.｡.:*･ﾟ
