Задача 578
Целые с уменьшающимися степенями простых множителей

Любое положительное целое число можно записать в виде произведения степеней простых множителей: p1a1 × p2a2 × ... × pkak,
где pi - различные простые целые числа, ai > 0 и pi < pj при i < j.

Положительное целое число с уменьшающимися степенями простых множителей - это такое число, для которого aiaj при i < j.
Например, 1, 2, 15=3×5, 360=23×32×5 и 1000=23×53 - целые числа с уменьшающимися степенями простых множителей.

Пусть C(n) будет количеством положительных целых чисел не больше n с уменьшающимися степенями простых множителей.
C(100) = 94, так как все положительные целые числа не более 100, кроме 18, 50, 54, 75, 90 и 98, имеют уменьшающиеся степени.
Известно, что C(106) = 922052.

Найдите C(1013).

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net