| Автор | Сообщение |
|
Отправлено: 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. Заголовок: Спасибо большое за п..
Спасибо большое за помощь Константин Юрьевич!
|
|
|
|
- участник сейчас на форуме
- участник вне форума