Форум » Массивы, сортировка, работа с файлами » Задача 101 Задание 25 » Ответить
Задача 101 Задание 25
nikitadvu: Среди целых чисел, принадлежащих числовому отрезку [125697;190234], найдите числа, которые представляют собой произведение двух различных простых делителей. Запишите в ответе количество таких чисел и максимальное их них. Написал программу,но выдаёт неправильный ответ,подскажите пожалуйста, что не так? [pre2]def Prime(n): d=2 while d*d<=n and n%d!=0: d+=1 return d*d>n def f(n): dl=[] sqrt=int(n**0.5) for j in range(2,sqrt+1): if Prime(j) and n%j==0: dl=dl+[j] if len(dl)==2: dl.sort() return dl count=0 mx=0 for i in range(125697,190234+1): k=1 for elem in f(i): k=k*elem if k==i: count+=1 if i>mx: mx=i print(count,mx)[/pre2]
Ответов - 10
Поляков: nikitadvu пишет: [pre2] for elem in f(i): k=k*elem[/pre2]Тут непонятны два момента. Во-первых, зачем вы для каждого числа заново считаете список простых чисел через функцию f? На это впустую тратится уйма времени. Во-вторых, почему вы думаете, что простые делители, входящие в состав числа, выбираются подряд из списка?
nikitadvu: Поляков пишет: Тут непонятны два момента. Во-первых, зачем вы для каждого числа заново считаете список простых чисел через функцию f? На это впустую тратится уйма времени. Во-вторых, почему вы думаете, что простые делители, входящие в состав числа, выбираются подряд из списка? Не подскажите как исправить?
Поляков: nikitadvu пишет: Не подскажите как исправить? Один из вариантов такой: 1) построили список простых чисел dels 2) в цикле перебираем все числа диапазона (for i in range) 3) для числа проверяем во вложенном цикле все простые делители (for d in dels) 4) если d - делитель i, то проверяем парный делитель i/d на простоту; если он тоже входит в список dels, то нашли подходящее число.
nikitadvu: Поляков пишет: 1) построили список простых чисел dels Непонятно как построить,заранее мы же не можем знать сколько должно быть в списке простых чисел;)
Поляков: nikitadvu пишет: Непонятно как построить,заранее мы же не можем знать сколько должно быть в списке простых чисел;) Вас интересуют только числа в диапазоне от 2 до iMax/2, где iMax = 190234. Их все нужно проверить на простоту и простые сохранить в списке. но сделать это один раз, до начала основного цикла перебора.
nikitadvu: Спасибо Константин Юрьевич за отклик на сообщение, всё дело в том, что я не знаю как мне перебрать числа из списка, который находиться в функции и которые конечно же не должны выбираться подряд,в поисках решения я нашёл похожую задачу 117 https://egekp.unoforum.pro/?1-22-15-00000013-000-0-0-1605448219, там был такой же фрагмент решения и почему то он прошёл и в этом решении если не ошибаюсь простые делители выбираются подряд из списка, вот как так может быть?
Поляков: nikitadvu пишет: я нашёл похожую задачу 117 https://egekp.unoforum.pro/?1-22-15-00000013-000-0-0-1605448219, там был такой же фрагмент решения и почему то он прошёл и в этом решении если не ошибаюсь простые делители выбираются подряд из списка Там простое число добавляется в произведение только тогда, когда обнаружено, что оно является делителем рассматриваемого числа.
nikitadvu: Константин Юрьевич,написал программу как вы говорили,но она работает слишком долго и выдаёт неправильное количество: [pre2] def Prime(n): d=2 while d*d<=n and n%d!=0: d+=1 return d*d>n iMax=190234 dels=[] for divs in range(2,(iMax//2)+1): if Prime(divs): dels=dels+[divs] count=0 mx=0 for i in range(125697,190234+1): flag=0 for d in dels: if i%d==0: if(i//d)in dels and i%(i//d)==0 and flag==0: count+=1 flag+=1 if i>mx: mx=i print(count,mx)[/pre2]
Поляков: nikitadvu пишет: and i%(i//d)==0 and flag==0: Вот этих манипуляций я не понял. Кажется, вы все усложнили. Вот это работает: [pre2] for i in range(125697,190234+1): for d in dels: if i % d == 0: if d != i//d and (i//d) in dels : count += 1 if i > mx: mx=i break[/pre2]
nikitadvu: Спасибо большое за помощь Константин Юрьевич!
полная версия страницы