Введение
В этом практическом занятии (lab) вы научитесь разлагать целое число на простые множители с помощью программы на языке C. В рамках практического занятия будут рассмотрены следующие шаги:
- Считывание целого числа, введенного пользователем.
- Реализация алгоритма для деления введенного числа на простые числа до полного разложения.
- Вывод простых множителей введенного числа.
По завершении этого практического занятия вы лучше поймете, как работать с целыми числами, простыми числами и базовыми концепциями программирования на языке 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(), где введенное число делится на простые числа до полного разложения. Затем простые множители выводятся на консоль.
