Автор | Сообщение |
|
Отправлено: 14.04.21 19:14. Заголовок: Задача 101 Задание 25
Среди целых чисел, принадлежащих числовому отрезку [125697;190234], найдите числа, которые представляют собой произведение двух различных простых делителей. Запишите в ответе количество таких чисел и максимальное их них. Написал программу,но выдаёт неправильный ответ,подскажите пожалуйста, что не так? 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)
|
|
|
Ответов - 10
[только новые]
|
|
|
| Администратор
|
Сообщение: 2702
|
|
Отправлено: 14.04.21 22:09. Заголовок: nikitadvu пишет: f..
nikitadvu пишет: цитата: | for elem in f(i): k=k*elem |
|
Тут непонятны два момента. Во-первых, зачем вы для каждого числа заново считаете список простых чисел через функцию f? На это впустую тратится уйма времени. Во-вторых, почему вы думаете, что простые делители, входящие в состав числа, выбираются подряд из списка?
|
|
|
|
Отправлено: 15.04.21 11:26. Заголовок: Поляков пишет: Тут ..
Поляков пишет: цитата: | Тут непонятны два момента. Во-первых, зачем вы для каждого числа заново считаете список простых чисел через функцию f? На это впустую тратится уйма времени. Во-вторых, почему вы думаете, что простые делители, входящие в состав числа, выбираются подряд из списка? |
| Не подскажите как исправить?
|
|
|
|
| Администратор
|
Сообщение: 2705
|
|
Отправлено: 15.04.21 11:58. Заголовок: nikitadvu пишет: Не ..
nikitadvu пишет: цитата: | Не подскажите как исправить? |
|
Один из вариантов такой: 1) построили список простых чисел dels 2) в цикле перебираем все числа диапазона (for i in range) 3) для числа проверяем во вложенном цикле все простые делители (for d in dels) 4) если d - делитель i, то проверяем парный делитель i/d на простоту; если он тоже входит в список dels, то нашли подходящее число.
|
|
|
|
Отправлено: 16.04.21 00:51. Заголовок: Поляков пишет: 1) п..
Поляков пишет: цитата: | 1) построили список простых чисел dels |
| Непонятно как построить,заранее мы же не можем знать сколько должно быть в списке простых чисел;)
|
|
|
|
| Администратор
|
Сообщение: 2710
|
|
Отправлено: 16.04.21 09:35. Заголовок: nikitadvu пишет: Неп..
nikitadvu пишет: цитата: | Непонятно как построить,заранее мы же не можем знать сколько должно быть в списке простых чисел;) |
|
Вас интересуют только числа в диапазоне от 2 до iMax/2, где iMax = 190234. Их все нужно проверить на простоту и простые сохранить в списке. но сделать это один раз, до начала основного цикла перебора.
|
|
|
|
Отправлено: 14.04.21 23:30. Заголовок: Спасибо Константин Ю..
Спасибо Константин Юрьевич за отклик на сообщение, всё дело в том, что я не знаю как мне перебрать числа из списка, который находиться в функции и которые конечно же не должны выбираться подряд,в поисках решения я нашёл похожую задачу 117 https://egekp.unoforum.pro/?1-22-15-00000013-000-0-0-1605448219, там был такой же фрагмент решения и почему то он прошёл и в этом решении если не ошибаюсь простые делители выбираются подряд из списка, вот как так может быть?
|
|
|
|
| Администратор
|
Сообщение: 2703
|
|
Отправлено: 15.04.21 06:12. Заголовок: nikitadvu пишет: я н..
nikitadvu пишет: Там простое число добавляется в произведение только тогда, когда обнаружено, что оно является делителем рассматриваемого числа.
|
|
|
|
Отправлено: 17.04.21 15:11. Заголовок: Константин Юрьевич,н..
Константин Юрьевич,написал программу как вы говорили,но она работает слишком долго и выдаёт неправильное количество: 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)
|
|
|
|
| Администратор
|
Сообщение: 2713
|
|
Отправлено: 18.04.21 20:23. Заголовок: nikitadvu пишет: and..
nikitadvu пишет: цитата: | and i%(i//d)==0 and flag==0: |
|
Вот этих манипуляций я не понял. Кажется, вы все усложнили. Вот это работает: 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
|
|
|
|
Отправлено: 19.04.21 15:19. Заголовок: Спасибо большое за п..
Спасибо большое за помощь Константин Юрьевич!
|
|
|
|