a = 244143
b = 1367821
k = 0
for n in range(a, b + 1):
ds = []
for d in range(2, n//2 + 1):
if n % d == 0:
ds.append(d)
if len(ds) > 3:
break
if len(ds) ==3:
print(n,ds[1],ds[2])
Полная версия: Задача егэ информатика
Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку 244143 1367821, числа, имеющие ровно 5 различных делителей. В ответе для каждого найденного числа запишите два его наибольших делителя, не равных самому числу, в порядке возрастания. Я написал вот такую программу. Но ответы, то ли не выводит, то ли долго считает. Напишите плиз где у меня ошибка.Заранее спасибо
if len(ds) > 5:
Да, моя ошибка, исправил но все равно считает очень долго
Естевенно, давайте еще подумаем 
вот вы пишете
А собственно говоря скуяли? если n делится на d без остатка то вполне логично что также n делится на результат этого деления тоже без остатка. тоесть при обнаружении что n % d == 0 мы можем в ds внести сразу два числа: d и n//d при условии что они не равны друг другу. И тогда нам уже не нужно пербирать все d от 2 до n//2+1 , а нужно перебиать всеголишь от 2 по int(sqrt(n))+1. Или пока d*d<=n
Что на порядки сократит скорость перебора. До 10-20 секунд.
Честно говоря, мне тяжело понять при чем тут информатика, тут чистая жи математика.
вот вы пишете
if n % d == 0: ds.append(d)
Что на порядки сократит скорость перебора. До 10-20 секунд.
Честно говоря, мне тяжело понять при чем тут информатика, тут чистая жи математика.
Можете пожалуйтса изменить мой код и скинуть
Просто когда я написал int(sqrt(n)) +1,то у меня просто начало выводить все числа
Просто когда я написал int(sqrt(n)) +1,то у меня просто начало выводить все числа
from math import sqrt a = 244143 b = 1367821 for n in range(a, b + 1): ds = [] for d in range(2, int(sqrt(n)) + 1): if n % d == 0: ds.append(d) if d != n//d: ds.append(n//d) if len(ds) >= 3: break if len(ds) ==3: ds.sort() print(n, ds[1],ds[2])
from math import sqrt a = 244143 b = 1367821 for n in range(a, b + 1): ds = [] if int(sqrt(n)) == sqrt(n): for d in range(2, int(sqrt(n)) + 1): if n % d == 0: ds.append(d) if d != n//d: ds.append(n//d) if len(ds) >= 3: break if len(ds) ==3: ds.sort() print(n, ds[1],ds[2])
Спасибо огромное!!!
+rep
Только можете еще раз обьяснить зачем n//d?
+rep
Только можете еще раз обьяснить зачем n//d?
Leeну смотри, ты перебираешь делитель d от 2 до n. Допустим n у тебя 36, для простоты.
Только можете еще раз обьяснить зачем n//d?
Вот ты взял 36 поделил на 2 (n%d) и оказалось что оно делиться без остатка.
ОК, записываем число 2 в делители.
НО у нас образовалось еще один делитель n//d (36/2=13) => 36/13=2, на которое число тоже делиться без остатка. И вовсе не обязательно ждать пока итератор дойдет до 13 чтобы и его тоже добавить в делитель. При таком подходе нужно перебирать числа не от 2 до n , а до корня квадратного из n. Что при порядке чисел в задании в тысячу раз уменьшает количество операций.
Тут больше математики чем програмирования, хотя при програмировании вот таким как раз приходиться заниматья.
Спасибо огромное!