檢查素數因子分解的素數

Question

我有以下用於素數分解的代碼。

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);    
} 

從數學的角度來看，我們必須檢查每個除數i是否也是素數，而不僅僅是因數。任何人都可以解釋我（數學）爲什麼算法仍然有效？

Answer 1

假設i不是素數;說i = j * k其中j和k小於i。這意味着當我們的循環達到i時，它已經首先達到j和k。並且在我們完成j的循環後，n不能再被j整除，因爲我們已經將所有j都計算在內了。同樣爲k。所以當我們爲i做循環時，我們知道n不能再被j或k整除;因此它不能被i整除。所以while循環從不執行。這意味着我們不需要對非素數i進行特殊檢查，因爲無論如何什麼都不會發生。