Основные факторы в C

Question

Я наткнулся на эту эффективную программу для печати всех простых множителей заданного числа:

# 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)
    {
        // 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&&n%2!=0)
        printf ("%d ", n);
}

/* Driver program to test above function */
int main()
{
    int n = 315;
    primeFactors(n);
    return 0;
}

Вывод 3 3 5 7. Это отлично.

Но у меня путаница в этом алгоритме.sqrt() возвращает значение с плавающей точкой.Если он отображается в целочисленном формате printf, он возвращает случайное большое число.Если это так, условие в цикле for должно не выполняться, потому что sqrt() в виде целого числа возвращает случайное число.Может кто-нибудь объяснить это?

Плюс, кто-то может это проверить?Этот алгоритм был неправильно написан на сайте Geeksforgeeks, как будто (n> 2) вместо if (n> 2 && n! = 0), который был добавлен мной.Кто-то, пожалуйста, проверьте этот алгоритм.Заранее спасибо.

Answer 1

Если вы попытаетесь напечатать значение sqrt(n) , как если бы было целым числом:

printf("sqrt(n) = %d\n", sqrt(n)); // Don't do this

, то у вас неопределенное поведение.sqrt() возвращает результат типа double.Компилятор не знает (или не обязан знать) ожидаемый тип аргумента.Вы должны передать аргумент правильного типа.Вышеупомянутый вызов printf имеет неопределенное поведение.

В других контекстах, где тип и ожидаемый тип выражения однозначны, язык требует неявных преобразований.В частности, в выражении i <= sqrt(n), где i и n имеют тип int, аргумент n преобразуется из int в double (тип параметра для sqrt()) , and the value of я is also converted from Int to double`.Результат, вероятно, будет тем, что вы ожидали.

Кстати, это:

for (int i = 3; i <= sqrt(n); i = i+2) ...

, скорее всего, будет неэффективным.Функция sqrt является относительно дорогой, и она будет вызываться на каждой итерации цикла.(Предварительный расчет sqrt(n) в некоторых случаях является хорошим решением, но здесь значение n может изменяться в цикле.)

Альтернатива:

for (int i = 3; i*i <= n; i += 2) ...

, которая позволяет избежатьСложности арифметики с плавающей точкой (но подумайте о том, может ли i*i переполниться).

(Было бы хорошо, если бы в C была целочисленная функция квадратного корня в стандартной библиотеке, но это не так.)

Answer 2

Другие предложили предварительно рассчитать целочисленный квадратный корень, но вам нужно быть осторожным, чтобы пересчитать его при необходимости.Для основного цикла я бы использовал что-то вроде:

// n must be odd at this point.  So we can skip 
// one element (Note i = i +2)
int limit = isqrt(n);  // Calculate integer square root.
for (int i = 3; i <= limit; i = i+2)
{
    // While i divides n, print i and divide n
    if (n % i == 0)
    {
        printf("%d ", i);
        n = n / i;

        while (n%i == 0)
        {
            printf("%d ", i);
            n = n / i;
        }

        // Recalculate limit as n has changed.
        limit = isqrt(n);
    }
}

Это пересчитывает квадратный корень только после изменения проверяемого числа.Я использую isqrt(n), чтобы указать функцию для выполнения фактического расчета.В моем собственном коде я использую Ньютона-Рафсона, но есть и другие возможные методы.

Ваш тест в конце может быть упрощен до:

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

Существует не более чем один простой коэффициент большечем квадратный корень из числа.Этот единственный фактор (если он присутствует) будет оставшимся после того, как все меньшие простые факторы были разделены.

Answer 3

Насколько я понимаю из вашего вопроса, вы передаете float в printf() функцию со спецификатором %d для integer.Это неопределенное поведение .

N1570 7.21.6.1 параграф 9:

... Если какой-либо аргумент не является правильным типом длясоответствующая спецификация преобразования, поведение не определено.

Вот почему вы видите значение мусора.Компилятор может предупредить вас, но не об ошибке ни времени компиляции, ни времени выполнения, поскольку C не является строго типизированным языком .

Он успешно скомпилирован, но выводится -376018152.Итак, еще раз, это UB.