Разложение целого числа на простые множители на языке C

Введение

В этом практическом занятии (lab) вы научитесь разлагать целое число на простые множители с помощью программы на языке C. В рамках практического занятия будут рассмотрены следующие шаги:

1. Считывание целого числа, введенного пользователем.
2. Реализация алгоритма для деления введенного числа на простые числа до полного разложения.
3. Вывод простых множителей введенного числа.

По завершении этого практического занятия вы лучше поймете, как работать с целыми числами, простыми числами и базовыми концепциями программирования на языке C.

Считывание целого числа

На этом шаге вы научитесь считывать целое число, введенное пользователем, в программе на языке C для разложения на простые множители. Мы создадим простую программу, которая попросит пользователя ввести число и сохранит его для дальнейшей обработки.

Сначала создадим новый файл на языке C в каталоге ~/project:

cd ~/project
nano prime_factorization.c

Теперь добавим следующий код для считывания целого числа:

#include <stdio.h>

int main() {
    int number;

    printf("Enter a positive integer to factorize: ");
    scanf("%d", &number);

    printf("You entered: %d\n", number);

    return 0;
}

Разберем код по частям:

• #include <stdio.h> подключает стандартную библиотеку ввода-вывода
• int main() - это главная функция, с которой начинается выполнение программы
• printf() используется для вывода приглашения пользователю
• scanf() считывает целое число, введенное пользователем
• %d - это спецификатор формата для целых чисел
• &number передает адрес памяти переменной number

Скомпилируйте и запустите программу:

gcc prime_factorization.c -o prime_factorization
./prime_factorization

Пример вывода:

Enter a positive integer to factorize: 24
You entered: 24

Деление на простые числа до полного разложения

На этом шаге вы измените предыдущую программу для реализации алгоритма разложения на простые множители. Мы обновим файл prime_factorization.c, чтобы разделить введенное число на простые числа до полного разложения.

Откройте существующий файл:

cd ~/project
nano prime_factorization.c

Замените предыдущий код следующей реализацией:

#include <stdio.h>

void factorize(int number) {
    printf("Prime factors of %d: ", number);

    // Start with the smallest prime number
    for (int divisor = 2; divisor <= number; divisor++) {
        while (number % divisor == 0) {
            printf("%d ", divisor);
            number /= divisor;
        }
    }

    printf("\n");
}

int main() {
    int number;

    printf("Enter a positive integer to factorize: ");
    scanf("%d", &number);

    // Check for valid input
    if (number <= 1) {
        printf("Please enter a number greater than 1.\n");
        return 1;
    }

    factorize(number);

    return 0;
}

Разберем алгоритм разложения на простые множители:

• Функция factorize() обрабатывает процесс разложения на простые множители
• Мы начинаем с наименьшего простого числа (2)
• Внешний цикл for пробует каждый потенциальный делитель
• Внутренний цикл while делит число повторно на текущий делитель
• Мы выводим каждый простой множитель по мере его нахождения
• Число обновляется с помощью целочисленного деления на каждой итерации

Скомпилируйте и запустите программу:

gcc prime_factorization.c -o prime_factorization
./prime_factorization

Примеры вывода:

Enter a positive integer to factorize: 24
Prime factors of 24: 2 2 2 3

Enter a positive integer to factorize: 100
Prime factors of 100: 2 2 5 5

Вывод простых множителей

На этом шаге вы улучшите программу для разложения на простые множители, чтобы получить более детальный и отформатированный вывод простых множителей. Мы изменим существующий файл prime_factorization.c, чтобы улучшить представление результатов.

Откройте файл:

cd ~/project
nano prime_factorization.c

Обновите код с улучшенной функцией разложения:

#include <stdio.h>

void factorize(int number) {
    int original_number = number;
    int factor_count = 0;

    printf("Prime Factorization of %d:\n", original_number);
    printf("---------------------\n");

    // Start with the smallest prime number
    for (int divisor = 2; divisor <= number; divisor++) {
        int current_factor_count = 0;
        while (number % divisor == 0) {
            number /= divisor;
            current_factor_count++;
            factor_count++;
        }

        // Print factors with their exponents
        if (current_factor_count > 0) {
            printf("%d^%d ", divisor, current_factor_count);
        }
    }

    printf("\n\nTotal number of prime factors: %d\n", factor_count);
}

int main() {
    int number;

    printf("Enter a positive integer to factorize: ");
    scanf("%d", &number);

    // Check for valid input
    if (number <= 1) {
        printf("Please enter a number greater than 1.\n");
        return 1;
    }

    factorize(number);

    return 0;
}

Основные улучшения в этой версии:

• Добавлено форматирование для отображения простых множителей
• Показывается показатель степени каждого простого множителя
• Подсчитывается общее количество простых множителей
• Сохраняется исходное введенное число для отображения

Скомпилируйте и запустите программу:

gcc prime_factorization.c -o prime_factorization
./prime_factorization

Примеры вывода:

Enter a positive integer to factorize: 24
Prime Factorization of 24:
---------------------
2^3 3^1
Total number of prime factors: 4

Enter a positive integer to factorize: 100
Prime Factorization of 100:
---------------------
2^2 5^2
Total number of prime factors: 4

Резюме

В этом практическом занятии (lab) вы научитесь считывать целое число, введенное пользователем, реализовывать алгоритм разложения на простые множители и выводить простые множители заданного числа. Ключевые шаги включают считывание целого числа, деление числа на простые числа до полного разложения и вывод простых множителей.

Программа сначала просит пользователя ввести положительное целое число, которое затем сохраняется в переменной. Алгоритм разложения на простые множители реализован в функции factorize(), где введенное число делится на простые числа до полного разложения. Затем простые множители выводятся на консоль.