@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], а также наименьшее из таких чисел. В ответе запишите два целых числа: сначала количество, затем наименьшее число.
  • Вопрос задан
  • 685 просмотров
Решения вопроса 1
@sand3001
Всего по немногу
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):
Собственно вопрос, почему вы при переборе делителей указываете интервал лишь до квадратного корня?
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
Vindicar
@Vindicar
RTFM!
По-моему, нет нужды проверять, простой ли делитель. Смотри, мы проверяем делители от 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. Но и без этого работает быстро.
Ответ написан
Комментировать
longclaps
@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))
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы