Python-сообщество

Lee · Март 26, 2021 10:53:21

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку 244143 1367821, числа, имеющие ровно 5 различных делителей. В ответе для каждого найденного числа запишите два его наибольших делителя, не равных самому числу, в порядке возрастания. Я написал вот такую программу. Но ответы, то ли не выводит, то ли долго считает. Напишите плиз где у меня ошибка.Заранее спасибо

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])

Отредактировано Lee (Март 26, 2021 11:07:07)

PEHDOM · Март 26, 2021 11:05:04

 if len(ds) > 5:

Почему 5? Я так понимаю, вы исключили деление на 1 и на само себя, по совету из предыдущего топика? . Ппочему 5 а не 3, если нужно“ числа, имеющие ровно 5 различных делителей” и мы знаем что любое число гарантировано имеет 2 делителя?

==============================
Помещайте код в теги:

[code python][/code]

Бериегите свое и чужое время.

Lee · Март 26, 2021 11:07:40

Да, моя ошибка, исправил но все равно считает очень долго

PEHDOM · Март 26, 2021 11:45:40

Естевенно, давайте еще подумаем
вот вы пишете

 if n % d == 0:
            ds.append(d)

А собственно говоря скуяли? если 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 секунд.
Честно говоря, мне тяжело понять при чем тут информатика, тут чистая жи математика.

==============================
Помещайте код в теги:

[code python][/code]

Бериегите свое и чужое время.

Отредактировано PEHDOM (Март 26, 2021 11:53:40)

Lee · Март 26, 2021 12:01:14

Можете пожалуйтса изменить мой код и скинуть
Просто когда я написал int(sqrt(n)) +1,то у меня просто начало выводить все числа

PEHDOM · Март 26, 2021 13:03:44

 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])

у меня занимает секунд 30, но можно еще ускорить в разы. Очевидно что нечетное количество делителей будет только когда у числа есть целый корень. тоесть сначала проверяем на корень квадратный, а потом если он есть считаем количество делителей. Занимает буквально пару секунд

 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])

==============================
Помещайте код в теги:

[code python][/code]

Бериегите свое и чужое время.

Отредактировано PEHDOM (Март 26, 2021 14:06:21)

Lee · Март 26, 2021 19:00:54

Спасибо огромное!!!
+rep
Только можете еще раз обьяснить зачем n//d?

Отредактировано Lee (Март 26, 2021 19:40:58)

PEHDOM · Март 26, 2021 20:15:34

Lee
Только можете еще раз обьяснить зачем n//d?

ну смотри, ты перебираешь делитель d от 2 до n. Допустим n у тебя 36, для простоты.
Вот ты взял 36 поделил на 2 (n%d) и оказалось что оно делиться без остатка.
ОК, записываем число 2 в делители.
НО у нас образовалось еще один делитель n//d (36/2=13) => 36/13=2, на которое число тоже делиться без остатка. И вовсе не обязательно ждать пока итератор дойдет до 13 чтобы и его тоже добавить в делитель. При таком подходе нужно перебирать числа не от 2 до n , а до корня квадратного из n. Что при порядке чисел в задании в тысячу раз уменьшает количество операций.
Тут больше математики чем програмирования, хотя при програмировании вот таким как раз приходиться заниматья.

==============================
Помещайте код в теги:

[code python][/code]

Бериегите свое и чужое время.

Отредактировано PEHDOM (Март 26, 2021 20:17:40)

Lee · Март 27, 2021 18:59:03

Спасибо огромное!

Python-сообщество

Уведомления

#1 Март 26, 2021 10:53:21

Задача егэ информатика

#2 Март 26, 2021 11:05:04

Задача егэ информатика

#3 Март 26, 2021 11:07:40

Задача егэ информатика

#4 Март 26, 2021 11:45:40

Задача егэ информатика

#5 Март 26, 2021 12:01:14

Задача егэ информатика

#6 Март 26, 2021 13:03:44

Задача егэ информатика

#7 Март 26, 2021 19:00:54

Задача егэ информатика

#8 Март 26, 2021 20:15:34

Задача егэ информатика

#9 Март 27, 2021 18:59:03

Задача егэ информатика

Board footer