素因数分解の方法素因数分解の計算 ある整数の素因数分解を考える時、すぐ思いつくのはその整数以下の素数で次々割っていくという方法です。 が、これだとまず素数を求める必要があり、これが厄介です。 そこで次に以下の様に、素因数分解したい数を2から整数の平方根までの数で次々割っていくという方法が考えられます。 (素朴試し割り法) なおここで紹介している方法は、最も単純な方法で素因数分解の方法としてはもっと洗練されたものがたくさんあります。 (i)素朴試し割り法の手順 素因数分解したい数 N を、まず一番小さな素数である２で割ります。 割り切れたら商( N/2 )をまた2で割ります。これを２で割り切れなくなるまで繰り返します。 この操作の結果残った数 R には素数2と2から作られる合成数(素数の積で表される数)は含まれなくなります。 素数2で割る操作の結果残った数を次に小さい素数3で割ります。これを3で割り切れなく
