factorization - 範囲内の数値の因数を取得する方法は?

Question

通常、素因数分解を行ってすべての素因数を取得し、順列と組み合わせを行ってすべての因数を見つけます。

例: 1824 は因数分解しようとしている数値です。ここで、300 の中に 1824 の因数が必要です。

何かコツはありますか？？

Answer 1

1 つのトリックは、因数を検索する数の平方根を超えた数を検索しないことです。たとえば、2 ～ 300 の因数を見つけるには、2 ～ 43 である 2-ceil(sqrt(1824)) から検索するだけで済みます。2 ～ 43 の範囲の数値を見つけたら、それを 1824 に分割して、43 を超える可能性のある他の要因を確認します。

Answer 2

力ずくの解決策として、この数を素因数分解する必要はありません。範囲内のすべての数値を簡単に確認できます。

因子を見つけたい数値の範囲を [range_start, range_end] とします。これらの数値をループで単純に反復し、各数値 ( x など) について ( ) をチェックnumber % x == 0し、 yes の場合、 x は数値の因数です。