11248. Простые на интервале

Заданы два натуральных числа b и c. Найдите такое наибольшее натуральное число a, что количество простых чисел на промежутке [a; b] включительно равно c.

Вход. Два целых числа b и c (b, c ≤ 10⁶).

Выход. Выведите искомое наибольшее значение a. Известно, что оно всегда существует.

Пример входа	Пример выхода
10 3	3

РЕШЕНИЕ

простые числа

Анализ алгоритма

Перебираем числа b, b – 1, b – 2, … . Подсчитываем среди них простые. Как только встретится c простых чисел, останавливаемся. Таким образом найдем макисмальное a, для которого на промежутке [a; b] имеется в точности c простых чисел.

Пример

Простыми числами на интервале [3; 10] будут 3, 5 и 7.

Реализация алгоритма

Функция IsPrime проверяет, является ли число n простым.

int IsPrime(int n)

{

for (int i = 2; i <= sqrt(n); i++)

if (n % i == 0) return 0;

return 1;

}

Основная часть программы. Читаем входные данные.

scanf("%d %d", &b, &c);

Начинаем движение переменной a от b по убыванию значений: b, b – 1, b – 2, … . В переменной cnt подсчитываем количество пройденных простых чисел. Как только оно станет равным c, выходим из цикла.

cnt = 0;

for (a = b; ; a--)

{

if (IsPrime(a)) cnt++;

if (cnt == c) break;

}

Выводим ответ.

printf("%d\n", a);