Рубрики

C Программа для эффективной печати всех простых факторов заданного числа

C Программы, Математика

Для числа n напишите эффективную функцию для вывода всех простых множителей n. Например, если введено число 12, тогда вывод должен быть «2 2 3». А если номер входа 315, то выход должен быть «3 3 5 7».
Ниже приведены шаги, чтобы найти все основные факторы.
1) Пока n делится на 2, выведите 2 и разделите n на 2.
2) После шага 1 n должно быть нечетным. Теперь начните цикл с i = 3 до квадратного корня из n. Пока i делит n, выведите i и разделите n на i, увеличьте i на 2 и продолжите.
3) Если n простое число и больше 2, то n не превратится в 1 за два вышеуказанных шага. Поэтому выведите n, если оно больше 2.

// C Программа для печати всех простых факторов
#include <math.h>
#include <stdio.h>

  
// Функция для печати всех простых множителей заданного числа n

void primeFactors(int n)

{

    // Вывести число 2, которые делят n

    while (n % 2 == 0) {

        printf("%d ", 2);

        n = n / 2;

    }

  

    // n должно быть нечетным в этой точке. Так что мы можем пропустить

    // один элемент (примечание i = i +2)

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

        // Пока я делю n, выводим i и делим n

        while (n % i == 0) {

            printf("%d ", i);

            n = n / i;

        }

    }

  

    // Это условие для обработки случая, когда n

    // простое число больше 2

    if (n > 2)

        printf("%d ", n);

}

  
/ * Программа драйвера для проверки вышеуказанной функции * /

int main()

{

    int n = 315;

    primeFactors(n);

    return 0;

}

Выход:

3 3 5 7

Как это работает?
Шаги 1 и 2 относятся к составным числам, а шаг 3 — к простым числам. Чтобы доказать, что полный алгоритм работает, нам нужно доказать, что шаги 1 и 2 действительно заботятся о составных числах. Это ясно, что шаг 1 заботится о четных числах. И после шага 1 все оставшиеся простые множители должны быть нечетными (разница двух простых множителей должна быть не менее 2), это объясняет, почему i увеличивается на 2.
Теперь основная часть заключается в том, что цикл продолжается до корня квадратного из n, а не до. Чтобы доказать, что эта оптимизация работает, рассмотрим следующее свойство составных чисел.
Каждое составное число имеет по крайней мере один простой множитель, меньший или равный квадратному корню из себя.
Это свойство может быть доказано с помощью встречного утверждения. Пусть a и b два таких фактора n, что a * b = n. Если оба больше √n, то ab> √n, * √n, что противоречит выражению «a * b = n».

На шаге 2 вышеприведенного алгоритма мы запускаем цикл и выполняем следующий цикл
а) Найти наименьший простой множитель i (должен быть меньше √n,)
б) Удалить все вхождения i из n, многократно разделив n на i.
c) Повторите шаги a и b для разделенных n и i = i + 2. Шаги a и b повторяются до тех пор, пока n не станет равным 1 или простому числу.

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

Рекомендуемые посты:

C Программа для эффективной печати всех простых факторов заданного числа

0.00 (0%) 0 votes