Матч 388, Гладкие числа (SmoothNumbers)

Дивизион 1, Уровень 1

Натуральное число называется k-гладким, если его наибольший простой делитель не больше k. Вычислить, сколько имеется k-гладких натуральных чисел, не больших n.

Класс: SmoothNumbers

Метод: int countSmoothNumbers(int n, int k)

Ограничения: 1 £ n £ 100000, 1 £ k £ 100.

Вход. Целые числа n и k.

Выход. Количество k-гладких натуральных чисел, не больших n.

Пример входа

n	k
10	3
15	3
5	20
100000	100

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

7

8

5

17442

РЕШЕНИЕ

перебор + разложение на множители

Задачу решим переборным способом. Для каждого натурального числа i от 1 до n выясним, лежат ли его простые множители в промежутке от 2 до k. Для этого переберем все делители числа i от 2 до k и разделим i на них. Если в результате получится 1, то число i является k-гладким. В переменной res подсчитываем количество k-гладких чисел.

ПРОГРАММА

#include <stdio.h>

class SmoothNumbers

{

public:

int countSmoothNumbers(int n, int k)

{

int temp, i, j, res = 0;

for(i = 1; i <= n; i++)

{

temp = i;

for(j = 2; j <= k; j++)

while(temp % j == 0) temp /= j;

res += (temp == 1);

}

return res;

}

};