Простое или составное число с использованием рекурсии

Введение

В этом лабе мы научимся писать программу на C, которая с использованием рекурсии проверяет, является ли число простым или составным. Простое число - это число, которое делится только на 1 и само на себя, в то время как составное число - это число, которое не является простым. Мы будем использовать рекурсию для написания программы, которая представляет собой метод решения задач путём их разбиения на более мелкие и простые задачи.

Skills Graph

Получение ввода от пользователя

Начнём с того, чтобы попросить пользователя ввести положительное целое число для проверки, является ли оно простым или составным, с использованием функции scanf. Добавьте следующий код в файл main.c внутри функции int main():

#include <stdio.h>

int main()
{
    int num;
    printf("Enter a positive integer: ");
    scanf("%d", &num);
    return 0;
}

Написание рекурсивной функции для проверки числа

В этом шаге мы напишем рекурсивную функцию для проверки, является ли число простым или составным. Эта функция принимает два аргумента: число для проверки и переменную-счётчик, которая начинается с числа, делённого на 2. Если счётчик достигает 1, функция возвращает 1, что означает, что число простое, иначе функция делает рекурсивный вызов самой себя с уменьшенной переменной-счётчиком. Если в какой-то момент число делится на переменную-счётчик без остатка, функция возвращает 0, что означает, что число составное. Добавьте следующий код в конец файла main.c:

int isPrime(int n, int c)
{
    if (c == 1) {
        return 1;
    } else {
        if (n % c == 0) {
            return 0;
        } else {
            return isPrime(n, c - 1);
        }
    }
}

Проверка и вывод результата

В этом шаге мы вызовем функцию isPrime для проверки, является ли число простым или составным. В зависимости от результата функции мы выведем соответствующее сообщение пользователю. Добавьте следующий код в конец файла main.c для завершения программы:

int main()
{
    int num, prime;
    printf("Enter a positive integer: ");
    scanf("%d", &num);
    prime = isPrime(num, num/2);
    if (prime == 1) {
        printf("%d is a prime number.\n", num);
    } else {
        printf("%d is a composite number.\n", num);
    }
    return 0;
}

Сборка и запуск программы

В этом шаге мы скомпилируем и запустим программу. Откройте терминал и перейдите в директорию, где находится файл main.c. Добавьте следующую команду в терминал для компиляции программы:

gcc main.c -o main

Добавьте следующую команду для запуска программы:

./main

Введите положительное целое число при запросе и нажмите Enter. Программа выведет, является ли число простым или составным.

Резюме

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