Требуется доказательство в части простой факторизации

Question

Согласно topcoder Link, нам нужно вычислить до квадратного корня числа, чтобы перечислить все его основные факторы ... Теперь я могу доказать в следующем коде, что мы делаем правильно пока мы не будем в цикле for. Но я не могу понять, почему оставшееся число будет простым, то есть после того, как мы выйдем из цикла, если if (n> 1) printf («% d», n); это то, что беспокоит меня ..! Можете ли вы дать мне официальное доказательство наряду с примерами ....

void factor(int n) 
{ 
    int i; 
    for(i=2;i<=(int)sqrt(n);i++) 
    { 
    while(n % i == 0) 
    { 
     printf("%d ",i); 
     n /= i; 
    } 
    } 
    if (n > 1) printf("%d",n); 
    printf("\n"); 
} 

Answer 1

Первоначально процесс переходит к поиску наименьшего коэффициента n меньше, чем его квадратный корень. Если у него его нет, то n является простым. Поэтому распечатайте n, так как это один из самых маленьких факторов!

Если вы найдете наименьший коэффициент, то он должен быть простым. Если нет, то он составной и имеет меньший простой фактор - противоречие.

Найдя наименьший простой коэффициент, разделим n на этот коэффициент, чтобы устранить его (помните, что может быть n == i*i*i*...i*r, где i - главный коэффициент, а r - остаток). Это то, что происходит внутри цикла while(n%i==0).

В конце этого срока у нас есть n с этим остатком. Итак, теперь нам нужен наименьший простой коэффициент r. Мы знаем, что наименьшим основным фактором будет i. Зачем? Поскольку, если r имел меньший простой множитель, чем i, то i не является наименьшим простым множителем n.

Итак, мы можем перейти к поиску i + 1 до sqrt (r) пробными подразделениями r, чтобы найти следующий наименьший простой коэффициент n. Если мы не найдем ни одного и г> 1, то г - последний простой множитель.

Продолжить индукцию.

После каждого раунда исключения (зайдите в петлю while(n%i==0)) у нас есть номер, который, как известно, не имеет простых коэффициентов < = i.

Answer 2

Грубо говоря, для каждого фактора i из n есть кофактор i' таким образом, что i*i'=n, а именно n/i. Без ограничения общности предположим, что i=min{i,i'}. Затем проходит i<=sqrt(n)<=i'. Реализация направлена ​​на поиск i только при игнорировании i'; достаточно места поиска для i.

Каждый вхождение фактора i отменяется n /= i заявление, что означает, что n заменяется на коэффициент i'. Здесь необходимо рассмотреть два случая. В первом случае этот коэффициент является простым, что означает, что в последовательных итерациях не будет обнаружено никаких факторов. Во втором случае коэффициент является составным; это означает, что он имеет коэффициент меньше sqrt(i')<sqrt(n).

Однако этот коэффициент должен быть больше i, так как все вхождения i были устранены путем петли while. Это означает, что остающийся фактор лежит между i+1 и sqrt(n), который будет найден в последовательных итерациях.