Матч 388, Трудные гладкие числа (SmoothNumbersHard)

Дивизион 2, Уровень 3

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

Класс: SmoothNumbers

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

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

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

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

Пример входа

n	k
10	3
15	3
123456	123

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

7

8

23855

РЕШЕНИЕ

разложение на множители

Сгенерируем при помощи решета Эратосфена массив primes длины n + 1, в котором положим primes[i] = 1, если i простое число (иначе primes[i] = 0). В ячейке mark[i] будем сохранять наибольший простой делитель числа i. По окончании заполнения массива mark подсчитаем число таких ячеек mark[i], для которых mark[i] £ k.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

class SmoothNumbersHard

{

public:

int countSmoothNumbers(int n, int k)

{

int i, j, res = 1;

vector<int> primes(n + 1), mark(n + 1);

for(i = 0; i <= n; i++) primes[i] = 1;

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

if (primes[i])

{

mark[i] = i;

for(j = 2; j * i <= n; j++)

primes[i * j] = 0, mark[i * j] = i;

}

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

if (mark[i] <= k) res++;

return res;

}

};