試し割り法
trial division
ある数が他の数の倍数であるかを割り算で調べる
その数の平方根まで試せばよい
ある数の倍数Nの素因数として$ \sqrt{N} が最大であるから
輪転因数分解: wheel factorization
手頃な素数2, 3, 5で試す
それらの積30を法として、1, 7, 11, 13, 17, 19, 23, 29と合同な数で割っていく
30までの素数と合同になるような数
対象となる素数は少なくなるように選びたい
2, 3, 5, 7を選ぶと210までの素数で試さないといけない
試し割り法にユークリッドの互除法の処理を組み合わせて加速する？あんも.icon