Question

Информатика 10класс 25б На вход передаётся 2 натуральных числа a и b, не превышающих 65536. Необходимо вывести через пробел все простые числа, заключённые в промежутке между a и b. Пример: Ввод: 11 32 Ответ: 13 17 19 23 29 31

Answer 1

Ответ:

Решето Эратосфена

Объяснение:

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>

#include <cstdio>

using namespace std;

int pr[1000077];

int main()

{

#ifdef _DEBUG

//freopen("input.txt", "r", stdin);

#endif // _DEBUG

int a, b;

cin >> a >> b;

if (a > b)

{

 swap(a, b);

}

for (int i = 2; i <= b; i++)

{

 if (pr[i] == 2)

 {

  continue;

 }

 pr[i] = 1;

 for (int j = i + i; j <= b; j += i)

 {

  pr[j] = 2;

 }

}

for (int i = a + 1; i < b; i++)

{

 if (pr[i] == 1)

 {

  cout << i << ' ';

 }

}

}

Answer 2

Для решения данной задачи можно использовать алгоритм перебора чисел от a до b и проверки их на простоту.

1. Сначала создадим функцию, которая будет проверять, является ли число простым. Для этого будем перебирать все числа от 2 до квадратного корня из числа и проверять, делится ли оно на одно из этих чисел без остатка. Если делится, то число не является простым и функция должна вернуть False. Если перебор чисел не дал результатов, то число является простым и функция должна вернуть True.

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

2. Далее, считываем значения a и b:

a, b = map(int, input().split())

3. Затем, перебираем все числа от a до b и проверяем их на простоту. Если число простое, выводим его:

for num in range(a, b + 1):
    if is_prime(num):
        print(num, end=' ')

Полный код программы:

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

a, b = map(int, input().split())

for num in range(a, b + 1):
    if is_prime(num):
        print(num, end=' ')

Пример работы программы:

Ввод: 11 32

Вывод: 13 17 19 23 29 31