Алгоритмы для поиска простых факторов

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

почему у нас i

Предположим, вам нужно найти коэффициенты 9. Напишите это следующим образом:

1 * 9  = 9
3 * 3  = 9

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

Сверху Вы можете видеть, как только вы доберетесь до строки, где находится 3 * 3, вам не нужно исследовать дальше. И обратите внимание, что это 3 является квадратом root из 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

Снова вы видите после квадрат root 6 нам не нужно исследовать дальше, поскольку он не даст нам НОВЫХ цифр в качестве факторов. Сверху, факторы 6: 1,2,3,4,6,9,12,18,36. А простые множители равны 2,3.

В приведенных выше 2 примерах я взял в качестве примера совершенные квадраты. Давайте возьмем другой пример, который не является идеальным квадратом, например, 24: Квадрат root из 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.