求素因的算法

Question

我发现用C语言编写的算法可以解决素数问题，但是我不明白为什么会有i

// Program to print all prime factors 
# include <stdio.h> 
# include <math.h> 

// A function to print all prime factors of a given number n 
void primeFactors(int n) 
{ 
    // Print the number of 2s that divide n 
    while (n%2 == 0) 
    { 
        printf("%d ", 2); 
        n = n/2; 
    } 

    // n must be odd at this point.  So we can skip  
    // one element (Note i = i +2) 
    for (int i = 3; i <= sqrt(n); i = i+2) // I don't get why i <= sqrt(n) here !??
    { 
        // While i divides n, print i and divide n 
        while (n%i == 0) 
        { 
            printf("%d ", i); 
            n = n/i; 
        } 
    } 

    // This condition is to handle the case when n  
    // is a prime number greater than 2 
    if (n > 2) 
        printf ("%d ", n); 
}

Answer 1

为什么我们有我

假设您需要找到9的因数。编写如下：

1 * 9  = 9
3 * 3  = 9

// 9 * 1 = 9 but it is the same case as first

从上方您可以看到直到3 * 3行，您无需进一步探索。请注意，此3是9的平方根。对于9，因子是1,3,9。

下一个示例36：

1 * 36 = 36
2 * 18 = 36
3 * 12 = 36
4 * 9 = 36
6 * 6 = 36
// No need to go further as the digits will repeat

再次看到平方根6之后，我们不需要进一步探索，因为它不会给我们新的数字作为因子。从上面看，因子6为1,2,3,4,6,9,12,18,36。素因子是2,3。

在以上两个示例中，我以完美正方形作为示例。让我们举一个不是完美正方形的不同示例，例如24：24的平方根是4点的东西。因此，我们将看到我们必须在4处停止。

1 * 24 = 24
2 * 12 = 24
3 * 8  = 24
4 * 6  = 24

// Stop not process further
// Even if proceeded the next line would be 6 * 4 = 24 but we have already obtained these numbers.

因此我们在sqrt（24）停下来。

总结：对于“ n”，如果我们无法在sqrt（n）之前找到质数，则可以保证，在sqrt（n）之上的数字将不包含n的任何质数。