素因数分解で素数を調べよう

Question

素因数分解のための次のコードがあります。私たちはそれぞれの除数iも素数であるといないことが要因である場合にのみかどうかを確認する必要が数学的な観点からは

public static void primeFactors(int n) 
{ 
    for (int i = 2; i <= Math.sqrt(n); i = i+1) 
    {  
     while (n%i == 0) 
     { 
      factors.add(i); 
      n = n/i; 
     } 
    } 

    if (n>2) { 
     factors.add(n); 
    } 
    System.out.println(factors);    
} 

。誰かが私に（数学的に）なぜアルゴリズムがまだ動作するのか説明できますか？

Answer 1

iがプライムではないとします。例えば、i = j * kjとkがi未満であるとします。つまり、ループがiに達すると、最初にjとkに達しています。そしてjのループを実行した後、jを既に除外しているので、jによってもはやnを割り切れることができなくなりました。 kについても同様です。したがって、iのループを実行すると、jまたはkで割り切れることはありません。したがって、iで割り切れるものではありません。したがって、whileループは決して実行されません。これは、非プライムiのための特別なチェックを行う必要はないということです。とにかく何も起こらないからです。