Вопрос Одно из 25-ых заданий на ЕГЭ по информатике

[kaffedra]

Всем привет. Хочу сразу извиниться, если выбрал не тот раздел.
Сегодня, буквально 3 часа назад, разбирал задание из ЕГЭ по информатике.
Задание вынесло меня из себя, ну ничего не пойму как и что.
Вроде всё верно, программа должна выводить нужные числа, но нет, ничего не выходит.
Прошу помощи от знающих людей. Ниже прикреплено задание и написанная мной программа на языке Python и их скриншоты.
Если вы напишите программу, которая выводит нужный ответ, и объясните, что да как, я буду очень признателен.

Пожалуйста, авторизуйтесь для просмотра ссылки.

Пожалуйста, авторизуйтесь для просмотра ссылки.

"В программе: k - счётчик, d - делитель, i - числа заданного промежутка"

 

[P0Z1T1V4iK28]

Я вообще не понял ТЗ, что за делители блять

 

[Pepe01]

Я вообще не понял ТЗ, что за делители блять

чётные

 

[P0Z1T1V4iK28]

чётные

так там нечетные

 

[kaffedra]

Я вообще не понял ТЗ, что за делители блять

По условию, нужно найти числа, у которых 5 нечётных и различных делителей. В 5-ой строке я проверяю условие, чтобы d являлся делителем числа i и чтобы d был нечётным.

 

[COVCHEG]

Если тебе нужно 5 нечетных делителей, то такими делителями будут какое-то простое число и 4 его последовательные степени(от 0 до 4).Задача специально сделана под это условие, а не твой брутфорс алгоритм

 

[hitogami]

Вообще хрень пойми, что ты делаешь.

for number in range(35 * 10 ** 6, 40 * 10 ** 6):
    
    # неч дел
    d = 0
    
    # если делить число само на себя
    if number % 2 != 0:
        d = 1
    
    # цикл от 3 до половины числа(т.к. после нет общий) с отступом 2, что дает только неч дел
    for i in range(3, int(number / 2) +1, +2):
        
        if number % i == 0:
            d += 1
        
        if d > 5:
            break
    
    if d == 5:
        print('число с 5 неч делителями', number)

 

[PAI]

Решение, приведённое выше, работает за (n^2)/2 > 5*10^11, что слишком долго для ЕГЭ. Кстати, на самом сайте РешуЕГЭ представлено решение за n*sqrt(n), в данном случае это >10^9, то есть на C++ будет работать где-то за минуту, а на Python - в несколько раз дольше. Возможно, самое оптимальное решение подразумевает факторизацию за log(n) и применение комбинаторики

 

[PAI]

import math
l = 35 * 10**6
r = 40 * 10**6
for i in range(l, r):
n = i
#n = 2^n * p^4
while(n % 2 == 0):
n = n // 2
s = int(math.sqrt(int(math.sqrt(n)))) #n ^ (1/4)
if(s * s * s * s == n):
flag = True
for j in range(2, int(math.sqrt(s)) + 1):
if(s % j == 0):
flag = False
break
if(flag == True):
print(i)
#35819648
#38950081
#39037448
#39337984

import math
l = 35 * 10**6
r = 40 * 10**6
for i in range(l, r):
n = i
#n = 2^n * p^4
while(n % 2 == 0):
n = n // 2
s = int(math.sqrt(int(math.sqrt(n)))) #n ^ (1/4)
if(s * s * s * s == n):
flag = True
for j in range(2, int(math.sqrt(s)) + 1):
if(s % j == 0):
flag = False
break
if(flag == True):
print(i)
#35819648
#38950081
#39037448
#39337984

Съехала табуляция

 

[mhalaider]

Полезная шутка есть

 

[PAI]

Полезная шутка есть

Посмотреть вложение 201305

Сорян, не шарю