Как решить эту задачу?

Question

[Kek145]

пишет ответ 6663 1004 хотя должен 15652 10002

def all_divs(y):
    divs = []
    for j in range(2, int(y**0.5)+1):
        if y % j == 0 and p(j) == True:
            divs.append(j)
            if j*j != y and p(y//j) == True:
                divs.append(y//j)
    return divs
def p(x):
    for i in range(2, int(x**0.5)+1):
        if x%i == 0:
            return False
    return True


a = 10001
b = 50000
count = 0
minimum = b

for i in range(a, b+1):
    if len(all_divs(i)) == 3:
        if i < minimum:
            minimum = i
        count += 1
print(count, minimum)

Назовём натуральное число подходящим, если у него ровно 3 различных простых делителя. Например, число 180 подходящее (его простые делители — 2, 3 и 5), а число 12 — нет (у него только два различных простых делителя). Определите количество подходящих чисел, принадлежащих отрезку [10 001; 50 000], а также наименьшее из таких чисел. В ответе запишите два целых числа: сначала количество, затем наименьшее число.

Answer 1

[Sand]

def all_divs(y):
    divs = []
    for j in range(2, int(y/2)+1):
        if y % j == 0 and p(j) == True:
            divs.append(j)
    return divs

У Вас в коде:
for j in range(2, int(y**0.5)+1):
Собственно вопрос, почему вы при переборе делителей указываете интервал лишь до квадратного корня?

Comments

[Vindicar]

Это имеет смысл, просто не в авторском алгоритме - наименьший простой делитель числа гарантированно будет меньше или равен квадратному корню из него. Если такого делителя нет, то само число простое.

[Sand]

Vindicar, наименьший будет, но эта функция для поиска всех делителей

[Vindicar]

Sand, ну я и написал - это имеет смысл, но не в авторском алгоритме.
Если бы автор делил исходное число на найденный делитель, и начинал цикл заново, (т.е. разлагал число на простые множители), то это имело бы смысл.
В противном случае корректным будет ваше решение с N/2.

[Sand]

Vindicar, кстати говоря, можно вот так:

def all_divs(y):
    divs = []
    for j in range(2, int(y**0.5)+1):
        if y % j == 0:
            if p(j):
                divs.append(j)
            if j*j != y and p(y//j):
                divs.append(y//j)
    return divs

Пошустрее должно

Answer 2

[Vindicar]

По-моему, нет нужды проверять, простой ли делитель. Смотри, мы проверяем делители от 2 до sqrt(N).
Это значит, что если у числа есть составной делитель, то мы сначала наткнёмся на делители этого составного делителя. Тогда мы можем их устранить простым алгоритмом.
Обрати внимание, делители храним не в списке, а в множестве (set), чтобы избежать двойных включений.

1. Берём проверяемое число N, создаём пустой набор делителей. Принимаем последний множитель K = 2.
2. Пока N > 1:
3.    Цикл по i от K до корня из N
4.        Если N делится на i, то i - делитель. Тогда
5.            Принимаем K = i, делим N нацело на i, добавляем i в набор найденных делителей, прерываем цикл 3.
6.    Если цикл 3. не был прерван, то текущее N - простое. Добавляем N в набор делителей, прерываем цикл 2.
7. Возвращаем построенный набор делителей.

Таким образом мы постепенно "устраняем" простые делители, от меньших к большим, пока число само не станет простым.
А дальше просто, в цикле от 10001 до 50001 выполняем алгоритм выше.

Также можно оптимизировать программу, заставив цикл 3 перебирать не все числа до корня из N, а заранее вычисленный список простых чисел до заданного максимального N. Но и без этого работает быстро.

Answer 3

[longclaps]

Комраду Sand приз зрительских симпатий за умение сделать из говнокода еще более тормозной говнокод.

N = 50_001
sieve = [0] * N
for p in range(2, N):
    if not sieve[p]:
        for i in range(p, N, p):
            sieve[i] += 1
print(sieve[10_001:].count(3), sieve.index(3, 10_001))

Comments

[Sand]

Не комраду longclaps приз зрительских симпатий за его гениальный код и непомерное стремление набросать своё мнение на вентилятор

[longclaps]

Sand, извини, дружище - ты не из тех, кто задаёт вопросы, ты - мастер ответов, но обратная связь не помешает )

[Sand]

longclaps, да ничего, единственное, не согласен вот с этим:

сделать из говнокода еще более тормозной говнокод

. В этом утверждении отсутствует существенная деталь:

сделать из не рабочего говнокода еще более тормозной, но рабочий говнокод

[longclaps]

Sand, пожалуй так.