Задача на C++
Простые числа
Выведите в порядке возрастания все простые числа на отрезке [l;r]. Оформите решение в виде функции bool isPrime(int n), проверяющей число на простоту, и функции vector primes(int l, int r), возвращающей список простых чисел на отрезке [l;r].
Входные данные: Дано два натуральных числа l и r (l≤r≤1000).
Выходные данные: Выведите ответ на задачу.
Примеры:
Ввод: 5 20
Вывод: 5 7 11 13 17 19
Требуется дописать фрагмент кода:
#include
#include
using namespace std;
bool isPrime(int n)
# начало фрагмента
vector primes(int l, int r)
# конец фрагмента
int main()
{
int l, r;
cin >> l >> r;
vector res = primes(l, r);
for (int i = 0; i < res.size(); ++i){
cout << res[i] << " ";
}
return 0;
}

Для решения задачи необходимо написать две функции:

1. bool isPrime(int n) — проверяет, является ли число n простым.

2. vector primes(int l, int r) — возвращает все простые числа на отрезке [l; r] в порядке возрастания.

Код для вставки во фрагмент

{
    if (n < 2)
        return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0)
            return false;
    }
    return true;
}
vector<int> primes(int l, int r) {
    vector<int> result;
    for (int i = l; i <= r; i++) {
        if (isPrime(i)) {
            result.push_back(i);
        }
    }
    return result;
}

Полное решение на C++

#include 
#include 
using namespace std;
bool isPrime(int n) {
    if (n < 2)
        return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0)
            return false;
    }
    return true;
}
vector<int> primes(int l, int r) {
    vector<int> result;
    for (int i = l; i <= r; i++) {
        if (isPrime(i)) {
            result.push_back(i);
        }
    }
    return result;
}
int main() {
    int l, r;
    cin >> l >> r;
    vector<int> res = primes(l, r);
    for (int i = 0; i < res.size(); ++i) {
        cout << res[i] << " ";
    }
    return 0;
}

Объяснение решения

1. Функция isPrime(int n)

Простое число — это натуральное число больше 1, которое делится без остатка только на 1 и само себя.

• Если n < 2, возвращаем false, поскольку 1 не является простым числом.

• Проверяем делители от 2 до квадратного корня из n.

• Если найден делитель, возвращаем false.

• Если делителей нет, возвращаем true.

2. Функция primes(int l, int r)

• Создаём пустой вектор result.

• Перебираем все числа от l до r включительно.

• Проверяем каждое число с помощью isPrime(i).

• Если число простое, добавляем его в вектор с помощью push_back(i).

• Возвращаем полученный вектор.

Пример работы

Ввод:

Вывод:

В этом диапазоне простыми являются числа 5, 7, 11, 13, 17 и 19.

Сложность алгоритма: $O((r-l+1)\sqrt r)$, поскольку для каждого числа проверяются делители не больше его квадратного корня.

При ограничении $r \leq 1000$ такое решение работает быстро и полностью соответствует условию задачи.