こんにちは、サポーターの佐藤です。
みなさんは素因数分解をするときどのように考えていますか？
おそらく2から順に素数で割れるかどうかを確認していると思います。
今回はどのような順序で素因数分解をするのが効率的かを教えたいと思います。
まず、2で割れるかどうかは偶数かどうかを見ればすぐできます。
3で割れるかどうかはそれぞれのけたの数を全て足したものが3の倍数かどうかを確認すると分かります。（例：1236の場合1+2+3+6=12は三の倍数より1236＝3×412）
5で割れるかどうかは皆さんすぐに確認できると思います。
7で割れるかどうかは実際に計算するしかないです。
それ以上は必要になることはあまりないです。
では、なぜ三の倍数はそれぞれのけたの数を全て足すだけで分かるのかを証明したいと思います。
それぞれのけたの数をa,b,c,d…とすると、整数はすべてa+b×10+c×100+d×1000…と表せる。
この整数を変形するとa+b+c+d+…+(b×9+c×99+d×999+…)となる。
これはa+b+c+d+…+3(b×3+c×33+d×333+…)なのでa+b+c+d…と三の倍数とのたし算です。
よって、a+b+c+d…が三の倍数の時、この整数は三の倍数になります。
ぜひ、素因数分解を瞬殺して周りと差をつけてください。
-
十二支
記事がありません
