11105. Полупростые H-числа

H-числами называются числа вида 4n + 1 (n – целое неотрицательное). Каждое H-число является или единицей (1), или простым, или составным.

H-число h называется простым, если оно не единица и может быть представлено в виде произведения H-чисел единственным способом: 1 * h. Все остальные H-числа называются составными.

Например, составными H-числами являются 5 × 5 = 25, 5 × 9 = 45, 5 × 13 = 65, 9 × 9 = 81.

Полупростыми H-числами называются составные H-числа, которые являются произведением только двух H-чисел. Например, 125 = 5 × 5 × 5 не является полупростым H-числом, так как оно является произведением трех H-чисел.

Вход. Каждая строка содержит H-число h, не большее 1000001. Последняя строка содержит 0 и не обрабатывается.

Выход. Для каждого теста вывести h и количество H - полупростых чисел между 1 и h включительно.

Пример входа

21

85

789

0

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

21 0

85 5

789 62

РЕШЕНИЕ

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

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

Множество чисел вида 4n + 1 (n – целое неотрицательное) замкнуто относительно умножения. Информацию о числе 4i + 1 будем хранить в primes[i]:

primes[i] = 1, если число 4i + 1 является h простым;

primes[i] = 0, если число 4i + 1 является h составным;

При помощи решета Эратосфена заполняем массив primes. При перемножении чисел 4i + 1 и 4j + 1, хранящихся соответственно в ячейках primes[i] и primes[j], результат заносится в ячейку 4ij + i + j, соответствующую произведению (4i + 1) * (4j + 1) = 16ij + 4i + 4j + 1 = 4 * (4ij + i + j) + 1.

В массиве semi_primes отмечаем все полупростые H-числа, устанавливая равными единице значения ячеек, которым соответствуют произведения простых H-чисел. Затем заносим все сгенерированные полупростые H-числа в явном виде в массив res, где они уже отсортированы по возрастанию.

Для выполнения запроса воспользуемся функцией upper_bound, выполняющей бинарный поиск на отсортированном массиве.

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

Объявим MAX и глобальные массивы.

#define MAX 250001

int primes[MAX],semi_primes[MAX],res[MAX],h,ptr;

Генерируем массив primes при помощи решета Эратосфена.

void gen_primes(void)

{

long long i, j;

memset(primes,1,sizeof(primes));

for(i = 1; 4 * i * i + 2 * i < MAX; i++)

if (primes[i])

for(j = i; 4 * i * j + i + j < MAX; j++) primes[4 * i * j + i + j] = 0;

primes[0] = 0;

}

int main(void)

{

long long i, j;

gen_primes();

Собираем информацию о полупростых числах в массиве semi_primes.

memset(semi_primes,0,sizeof(semi_primes));

for(i = 1; 4 * i * i + 2 * i < MAX; i++)

for(j = i; 4 * i * j + i + j < MAX; j++)

if (primes[i] && primes[j])

semi_primes[4 * i * j + i + j] = 1;

Заносим все полупростые H-числа в явном виде в массив res.

for(ptr = -1, i = 1; i < MAX; i++)

if (semi_primes[i]) res[++ptr] = 4 * i + 1;

Выполняем запросы, выводим результат.

while(scanf("%d",&h),h)

printf("%d %d\n",h,upper_bound(res,res+ptr,h) - res);

return 0;

}