8549. Различные простые

Счастливыми назовем положительные целые числа, которые имеют хотя бы три различных простых делителя. Например 30 и 42 первые два счастливых числа. По заданному натуральному числу n следует найти n-ое счастливое число.

Вход. Первая строка содержит количество тестов t. Каждая из следующих t строк содержит одно целое число n (n ≤ 2 * 10⁶).

Выход. Выведите t строк, каждая из которых содержит счастливое число для соответствующего теста.

Пример входа	Пример выхода
2 1 2	30 42

РЕШЕНИЕ

решето делителей

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

Построим массив deg[i], который содержит:

· 0, если число i простое;

· количество разных простых делителей числа i, если i составное;

Например, deg[3] = deg[5] = deg[11] = 0, так как 3, 5 и 11 простые. deg[10] = 2, так как 10 = 2 * 5 и имеет 2 разных делителя. deg[8] = 1, так как 8 имеет один простой делитель. Также deg[p^a] = 1 для простого p и a > 1.

Элементы массива deg можно вычислить при помощи решета, напоминающего решето Эратосфена.

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

deg[i] содержит количество разных простых делителей числа i.

ans[i] будет содержать i-ое счастливое число.

#define MAX 3100000

int deg[MAX], ans[MAX];

Функция sieve строит массив deg, а затем массив ans.

void sieve(void)

{

int i, j, ptr = 1;

memset(deg,0,sizeof(deg));

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

Если i простое (deg[i] = 0), то все значения deg[i * j] (j = 2, 3, …) увеличим на единицу. Этим самым мы учитываем, что в числе i * j имеется простой делитель i.

if (deg[i] == 0)

for(j = 2 * i; j < MAX; j += i) deg[j]++;

Все числа i, имеющие не менее 3 делителя, в отсортированном виде заносим в массив ans.

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

if (deg[i] >= 3) ans[ptr++] = i;

}

Основная часть программы. Функция sieve заполняет массив ответов ans.

sieve();

Читаем количество тестов tests.

scanf("%d",&tests);

Обрабатываем последовательно тесты. Читаем значение n и выводим ответ ans[n].

while(tests--)

{

scanf("%d",&n);

printf("%d\n",ans[n]);

}