Задача с Тинькофф.

Назовем число хорошим, если число является составным, а количество делителей простое число.
Найти количество хороших чисел на диапазоне [l, r] 1<=l<=r<=10^14.

Решение:
Заметим, что число n называется хорошим, если n=p^a
Где p-простое число и a>1.

Для тех кто не знают тут надо смотреть формулу количество делителей, и подумать в каких ситуациях это выражение простое.

Стоит обратить внимания, что a+1 должно быть простым числом.

Отсюда следует что p<=10^7. Так как a>1.
С помощью решето Эратосфена найдем все простые числа на отрезке [1, 1е7]
Переберем каждое простое число - так мы зафиксируем ‘p’. Осталось найти все такие ‘a’, что

l<=p^a<=r
a>1
a+1=простое число

Если вы будете перебирать ‘a’ в цикле (или раз за разом умножать переменную на p) то у вас будет переполнение типа и получите WA. Например возьмем p=1e7 когда будете возводить в третью степень произойдет переполнение. Да вы могли остановиться заранее и не возводить в степень, но как это понять ?

Нужно поступить иначе, давайте найдем максимальную степень b, что
p^b<=r, для этого мы просто будем делить r на p пока не станет равным нулю, от количество делений мы можем найти b.

Аналогично найдем максимальную степень d, что
p^d<=l-1.

Получаем, что нас интересует в качестве степень ‘a’ все простые числа на [d+1, b]. Благо этот отрезок очень маленький и можно честно перебрать там, проверяю что число простое используя посчитанную решето.