Python

ЕГЭ информатика python

Назовём натуральное число подходящим, если у него ровно 3 различных простых делителя. Например, число 180 подходящее (его простые делители — 2, 3 и 5), а число 12 — нет (у него только два различных простых делителя). Определите количество подходящих чисел, принадлежащих отрезку [10 001; 50 000], а также наименьшее из таких чисел. В ответе запишите два целых числа: сначала количество, затем наименьшее число.

Как написать ето на питоне ебучем
Анатолий Алещенко
Анатолий Алещенко
704
cnt, mn = 0, 0
for n in range(10001, 50001):
~~i, k, c = 2, n, {}
~~while i <= k:
~~~~while k % i == 0: k, c[i] = k // i, 1
~~~~i += 1
~~if k != 1: c[k] = 1
~~if len(c) == 3: cnt, mn = cnt + 1, mn or n
print(cnt, mn)
РВ
Рамиль Вильданов
74 358
Лучший ответ
Я предлагаю традиционно - через сито Эратосфена. Сначала при помощи решета Эратосфена вычисляется список из всех простых чисел в диапазоне [0; 224] (простыми делителями, например, числа 50000, не говоря уж о числах меньше него, могут быть ведь только числа из этого диапазона, не так ли?). Потом все числа из диапазона [10001; 50000] последовательно делятся на элементы вычисленного списка простых чисел. Если у элемента оказывается ровно три простых делителя, он записывается в список подходящих чисел. В конце выводится длина списка всех подходящих чисел, то есть их количество в [10001; 50000] и первый подходящий элемент, который и будет минимальным. В общем, получается 7451 подходящих чисел всего, а минимальное из них, имеющее ровно 3 простых делителя (2, 41 и 46), это 10004.
DF
Dan Frank
29 440
Dan Frank Внизу - запоздалое исправление моей вчерашней ошибочной программы, которое, наверное, ужé ни к чему, так как у Алекса сделано ведь всё равно лучше! А первый код из трёх вариантов получился самым медленным и отстойным, хотя результаты выдаются правильные!. ))
Еще вариант:
from time import time
stt=time()#print(time()-stt,'\n')#

#-----------------------------------------

def Factor(n):
~~~~Ans = []
~~~~d = 2
~~~~while d * d <= n:
~~~~~~~~if n % d == 0:
~~~~~~~~~~~~Ans.append(d)
~~~~~~~~~~~~n //= d
~~~~~~~~else:
~~~~~~~~~~~~d += 1
~~~~if n > 1:
~~~~~~~~Ans.append(n)
~~~~return Ans
#-----------------------------------------

z0,z1 = 10_001, 50_000
n_ok = 0
mn_ok = 0
for z in range(z0,z1+1):
~~~~if len(set(Factor(z))) == 3:
~~~~~~~~n_ok += 1
~~~~~~~~if not mn_ok:
~~~~~~~~~~~~mn_ok = z

print(n_ok, mn_ok)

print(time()-stt,'\n')#stt=time()#

Результат работы:
15652 10002
0.6200785636901855

>>>
ДЕ
Дмитрий Евсеев
21 729
Dan Frank Когда я вчера минут через десять прочитала свой ответ, то обнаружила в нём грубую ошибку. Однако исправлять не стала специально, оставив это дело на потом. Не знаю как у кого, а у меня перед сном есть более весёлые и интересные дела чем программирование.
Сегодня я решила сравнить все три варианта по быстродействию. Компьютер считает быстро, так что лучше воспользоваться телефоном, решила я, с не очень быстрым приложением вроде Py³, где отличие видно сразу и оно разительное! Итак, есть мой (естественно исправленный!) вариант, а также первый и последний. Результаты во всех одинаковые. Но мой вариант считался минуту с лишним, последний - какие-то секунды, а вот самый первый вариант просчитался целых 10 минут!!! Ну и ну, вот тебе на! В общем, пока Аleks Nots у нас - чемпион :-)

Похожие вопросы