Краткая концепция: если у числа нечётное кол-во делителей, значит из него можно извлечь квадратный корень.
Дело в том, что если X/A=B, то X/B=A - т.е., обнаружив один делитель, мы сразу обнаруживаем другой. Таким образом мы постоянно будем находить пары делителей. Однако, согласно условию задачи, делителей должно быть 5. Такое возможно лишь тогда, когда одним из делителей будет квадратный корень числа: X/A=A
Исходя из этого, нам нет смысла рассматривать числа в этой задаче, из которых не извлекается квадратный корень, а для этого проведём небольшую аналитику: найдём все целые квадратные корни чисел на этом отрезке: Квадратный корень числа 63000000 примерно равен 7937.2, а значит внутри этого отрезка начнутся значения от 7937.
Найдём теперь квадратный корень правой границы: 103000000 и он примерно будет равен 10148.9. Подытожим: на нашем отрезке есть значения в квадрате чисел от 7938 до 10148 - именно на этом отрезке мы и будем искать ответы.
Сам код:
last=0
count=0
for i in range (7938,10148):
number=i**2
for j in range (2,i):
if number%j==0:
count+=2
if last==0:
last=number/j
if count==2:
print(f'{i**2} - само число и его наибольший нетривиальный делитель = {int(last)} ')
count=0
last=0
Разберём некоторые моменты:
for j in range (2,i): - мы запускаем цикл нахождения всех делителей, при этом тривиальные (1 и само число) мы не будем находить, а лишь учтём, что они будут у каждого числа, таким образом, из 5 нужных делителей, 2 уже известны и в подсчётах не участвуют. Также один из делителей будет квадратный корень числа, который мы также учли и в вычислениях не используем. Получается, что нам осталось найти числа, у которых 2 делителя, без учёта квадратного корня и тривиальных.
Именно поэтому в строке if count==2 - сравнивается count с 2
(Переменная count - количество найденных делителей)
if number%j==0:
count+=2 - Исходя из логики, описанной ранее: если X/A=B, то X/B=A - получаем, что при нахождении одного делителя, мы автоматически знаем о существовании второго, именно поэтому count увеличивается на 2.
Переменная last хранит в себе значение наибольшего нетривиального делителя. Чтобы его получить, надо найти наименьший делитель и разделить наше число на него, что мы и делаем.
Ответ на задачу:
88529281 - само число и его наибольший нетривиальный делитель = 912673
P.S. Если вы готовитесь к ЕГЭ, то настоятельно рекомендую изучить эту тему получше и самому попрактиковаться
1 votes Thanks 1
brshtsk
Здравствуйте! Спасибо за подробный ответ)) Но ваш код находит число с пятью нечетными делителями, а нужно найти с пятью четными
rinatmuxekto86
О, я упустил этот момент решения, мой код находил просто число с 5ю делителями, не акцентируя внимание на чётность/нечётность, сейчас поправим
brshtsk
for i in range(100000000 // 2, 180000000 // 2 + 1): if (i * 2) % 1000000 == 0: print("(", (i * 2) // 1000000, ")") if i % 2 == 1: if (i ** 0.5) % 1 == 0: k = 3 for q in range(3, int(i ** 0.5), 2): if i % q == 0: k += 2 if k > 5: break if k == 5: print(i * 2)
brshtsk
У меня получилось!! Только коэффиценты другие)
brshtsk
for i in range(63000000 // 2, 103000000 // 2 + 1): if (i * 2) % 1000000 == 0: print("(", (i * 2) // 1000000, ")") if i % 2 == 1: if (i ** 0.5) % 1 == 0: k = 3 for q in range(3, int(i ** 0.5), 2): if i % q == 0: k += 2 if k > 5: break if k == 5: print(i * 2)
brshtsk
Написал, основываясь на том, что если нам нужно найти число с 5 четными делителями, то оно равно числу с 5 нечетными делителями, увеличенному в два раза. Искал числа с 5 нечетными делителями, основываясь на том, что один делитель - корень числа, это вы верно написали)) Спасибо за уделенное время!!
Answers & Comments
Краткая концепция: если у числа нечётное кол-во делителей, значит из него можно извлечь квадратный корень.
Дело в том, что если X/A=B, то X/B=A - т.е., обнаружив один делитель, мы сразу обнаруживаем другой. Таким образом мы постоянно будем находить пары делителей. Однако, согласно условию задачи, делителей должно быть 5. Такое возможно лишь тогда, когда одним из делителей будет квадратный корень числа: X/A=A
Исходя из этого, нам нет смысла рассматривать числа в этой задаче, из которых не извлекается квадратный корень, а для этого проведём небольшую аналитику: найдём все целые квадратные корни чисел на этом отрезке: Квадратный корень числа 63000000 примерно равен 7937.2, а значит внутри этого отрезка начнутся значения от 7937.
Найдём теперь квадратный корень правой границы: 103000000 и он примерно будет равен 10148.9. Подытожим: на нашем отрезке есть значения в квадрате чисел от 7938 до 10148 - именно на этом отрезке мы и будем искать ответы.
Сам код:
last=0
count=0
for i in range (7938,10148):
number=i**2
for j in range (2,i):
if number%j==0:
count+=2
if last==0:
last=number/j
if count==2:
print(f'{i**2} - само число и его наибольший нетривиальный делитель = {int(last)} ')
count=0
last=0
Разберём некоторые моменты:
for j in range (2,i): - мы запускаем цикл нахождения всех делителей, при этом тривиальные (1 и само число) мы не будем находить, а лишь учтём, что они будут у каждого числа, таким образом, из 5 нужных делителей, 2 уже известны и в подсчётах не участвуют. Также один из делителей будет квадратный корень числа, который мы также учли и в вычислениях не используем. Получается, что нам осталось найти числа, у которых 2 делителя, без учёта квадратного корня и тривиальных.
Именно поэтому в строке if count==2 - сравнивается count с 2
(Переменная count - количество найденных делителей)
if number%j==0:
count+=2 - Исходя из логики, описанной ранее: если X/A=B, то X/B=A - получаем, что при нахождении одного делителя, мы автоматически знаем о существовании второго, именно поэтому count увеличивается на 2.
Переменная last хранит в себе значение наибольшего нетривиального делителя. Чтобы его получить, надо найти наименьший делитель и разделить наше число на него, что мы и делаем.
Ответ на задачу:
88529281 - само число и его наибольший нетривиальный делитель = 912673
P.S. Если вы готовитесь к ЕГЭ, то настоятельно рекомендую изучить эту тему получше и самому попрактиковаться
if (i * 2) % 1000000 == 0:
print("(", (i * 2) // 1000000, ")")
if i % 2 == 1:
if (i ** 0.5) % 1 == 0:
k = 3
for q in range(3, int(i ** 0.5), 2):
if i % q == 0:
k += 2
if k > 5:
break
if k == 5:
print(i * 2)
if (i * 2) % 1000000 == 0:
print("(", (i * 2) // 1000000, ")")
if i % 2 == 1:
if (i ** 0.5) % 1 == 0:
k = 3
for q in range(3, int(i ** 0.5), 2):
if i % q == 0:
k += 2
if k > 5:
break
if k == 5:
print(i * 2)