Найдите N-е наименьшее число, имеющее ровно 4 делителя

Дана натуральное число N , задача состоит в том, чтобы найти N -е наименьшее число в последовательности, имеющее ровно 4 делителя.

Примеры:

Input: 4
Output: 14
Explanation: The numbers in the sequence that has 4 divisors are 6, 8, 10, 14, …, the fourth number in the sequence is 14.

Input: 24
Output: 94

Подход: Эту проблему можно решить, заметив, что число i имеет простую факторизацию p1 ^a1 * p2 ^a2 * p3 ^a3 … pk ^ak , тогда число делителей i равно (a1+1)(a2+1)…( ак+1). Таким образом, чтобы у i было ровно 4 делителя , оно должно быть равно произведению двух различных простых чисел или некоторого простого числа, возведенного в степень 3 . Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте массивы divs[] и vis[] для хранения количества делителей любого числа и для проверки, считается ли данное число или нет соответственно.
• Инициализируйте переменную cnt как 0 , чтобы хранить количество элементов, имеющих ровно 4 делителя.
• Теперь используйте алгоритм решета Эратосфена.
• Итерировать, пока cnt меньше n, используя переменную, которую я начинаю с 2 :
  • Если я простой:
    • Выполните итерацию в диапазоне [2*i, 1000000], используя переменную j с приращением i :
      • Если число j уже рассмотрено, то продолжаем .
      • Обновите vis[j] как true и инициализируйте переменные currNum как j и подсчитайте как 0.
      • Разделите currNum на i , пока currNum % i равно 0, увеличьте div[j] и подсчитайте на 1.
      • Если currNum равно 1, count равно 3 и divs[j] равно 3, то cnt увеличивается на 1.
      • В противном случае, если currNum не равен 1, count равен 1, divs[j] равен 1 и divs[currNum] равен 0, то cnt увеличивается на 1.
      • Если cnt равно N, то выведите j и верните .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(Nlog(log(N))), где N равно 1000000 .
Вспомогательное пространство: O(N)