Степени простых чисел

[Alexey_Zotov30]

Здравствуйте, завсегдатаи форума и новички
Я бы хотел задать вопрос:
Мне необходимо найти количество чисел от 1 до n которые будут иметь нечетное число делителей. Например 4 имеет 3 делителя - 1,2,4. Зная, что такие числа образуются путем возведения простых чисел в четную степень в их произведении (2**2 = 4, 3**2 = 9, 2**2 * 3**2 = 36 и т.д.), я хочу генерировать эти числа пока не дойду до n и потом могу посчитать сколько их было, но я не понимаю какой квадрат простого числа добавлять на каждом шаге чтобы идти по возрастанию. Например, чтобы получить первое число с нечетным числом делителей мы возводим простое число 2 во 2 степень = 4, следующее по возрастанию будет 3 во 2 степени = 9, но следующее по возрастанию будет НЕ 5 во 2 степени = 25, а 2 в 4 степени = 16 и только потом идет 5 во 2 степени. Какой есть алгоритм чтобы пройтись по возрастанию по всем числам с нечетным числом делителей используя произведение простых чисел в четных степенях?

[ИСН]

Да, существует. Он проще, чем вы думаете.

[wrest]

Alexey_Zotov30 в сообщении #1630908 писал(а):

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

У вас устаревшие сведения. Любой квадрат (и только он) имеет нечётное количество делителей. Ессно, речь про натуральные числа.
Идущие подряд квадраты удобно вычислять как частичную сумму первых нечётных чисел, просто накапливаяя её.
$1+3=4$
$4+5=9$
$9+7=16$
И так далее.

[Ende]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы)

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.