Напишите рекурсивную функцию, которая подсчитывает количество простых чисел, не превышающих заданное натуральное число x. На языке программирования C++ и используя пространство…

Чтобы написать рекурсивную функцию на языке C++, которая подсчитывает количество простых чисел, не превышающих заданное натуральное число x, нужно сначала понять, что такое простое число. Простое число — это натуральное число больше 1, которое не имеет делителей, кроме 1 и самого себя.

Шаги для реализации:

1. Понять, что такое простое число:

   • Простые числа начинаются с 2, и следующие простые числа: 3, 5, 7, 11, и так далее.
   • Число считается простым, если оно не делится нацело ни на одно число, кроме 1 и самого себя.

2. Рекурсивная функция:

   • Нам нужна функция, которая будет проверять каждое число от 2 до x, чтобы определить, является ли оно простым.
   • Основная идея заключается в том, чтобы создать вспомогательную рекурсивную функцию, которая будет проверять, простое ли данное число, и так же считать количество простых чисел.

3. Основная функция:

   • Эта функция будет итерировать от 2 до x, сверяя каждое число с вспомогательной функцией.

Вот код с пояснениями:

#include <iostream>
using namespace std;

// Вспомогательная рекурсивная функция для проверки, является ли n простым числом
bool isPrime(int n, int divisor = 2) {
    // Если n меньше 2, оно не может быть простым
    if (n < 2) return false;
    // Если divisor достиг n, значит n - простое число
    if (divisor * divisor > n) return true;
    // Если n делится на divisor, оно не простое
    if (n % divisor == 0) return false;
    // Рекурсивный вызов, увеличивая делитель
    return isPrime(n, divisor + 1);
}

// Рекурсивная функция, подсчитывающая количество простых чисел от 2 до x
int countPrimes(int x) {
    // Базовый случай: если x меньше 2, простых чисел нет
    if (x < 2) return 0;
    // Рекурсивный случай: проверяем, является ли x простым
    return (isPrime(x) ? 1 : 0) + countPrimes(x - 1);
}

int main() {
    int x;
    cout << "Введите натуральное число x: ";
    cin >> x;

    int count = countPrimes(x);
    cout << "Количество простых чисел, не превышающих " << x << ": " << count << endl;

    return 0;
}

Объяснение кода:

1. Функция isPrime(int n, int divisor = 2):

   • Эта функция проверяет, является ли число n простым.
   • Она принимает число n и делитель divisor, который по умолчанию равен 2.
   • Функция возвращает false, если n меньше 2.
   • Если divisor * divisor больше n, значит, n простое.
   • Если n делится на divisor, то n не является простым.
   • В противном случае функцией вызывается сама себя с увеличенным divisor.

2. Функция countPrimes(int x):

   • Эта функция подсчитывает количество простых чисел от 2 до x.
   • Если x меньше 2, возвращается 0.
   • В противном случае функция проверяет, является ли x простым, добавляет 1 (если да) и рекурсивно вызывает себя с x - 1.

3. Функция main():

   • Вводит значение x и выводит количество простых чисел, не превышающих x.

Этот код является простым и удобным для понимания, а также иллюстрирует основу рекурсии и проверку простоты чисел.