(Оффтоп)
Батороев, искренне желаю удачи, вот только боюсь, что алгоритм Евклида там не прокатит. И формула включений-исключений тоже, если что (это чтоб Вы зря не мучились).
Насчет алгоритма Евклида Вы правы. А вот относительно формул включения-выключения я бы не был столь категоричным.
Любое нечетное число можно разложить на разность квадратов двух последовательных чисел:

В отношении рассматриваемых чисел это выглядит следующим образом:

Поэтому в отношении рассматриваемых чисел можно утверждать, что каждое простое или составное число

при перестановке членов равенства дает большее число такого же вида:

но уже гарантированно составное (т.к.

и

- не два последовательных числа).
Количество таких чисел до

:

(1)
Исходное число условно назовем "прародителем".
Любое составное нечетное число кроме того раскладывается на разность квадратов:

Аналогично раскладывая составные числа вида

, а затем переставляя члены равенства, будем получать другие составные числа. Величина вновь получаемых чисел по сравнению с исходным числом зависит от величины меньших множителей данных чисел.
Например,

Получаем:


, т.к.

.

Получаем:


, т.к.

Из примера видно, что одним из полученных из составного числа является меньшее число (в данном случае

), которое является для числа

"прародителем".
Таким образом, составные числа

, имеющие

простых множителя, могут в свою очередь быть "прародителем" всего одного числа, т.к. из двух получаемых чисел одно является "прародителем" самого числа.
Как считать количество других получаемых чисел

(в примере - число

)? Пока не знаю. По-видимому, используя каким-то образом формулы включений-выключений.
Но почти уверен, что
(где

- число всех чисел вида

, непревосходящих

).
Попутно отмечу, что существуют "самородящиеся" составные числа, например:

Каждое из них уменьшает на единицу выражение (1). Интересно, много ли таких?