DjangoBB LoFi version

Lee

Март 31, 2021 11:40:31

Дана последовательность чисел от 45000000 до 50000000. Нужно вывести все числа которые имеют ровно 5 различных нечетных делителя. Я написал вот такую программу, но она не работает. Исправьте пожалуйста. Заранее спасибо

[code python]from math import sqrt
a = 45000000
b = 50000000
k=0
for n in range(a, b + 1):
    ds = []
    for d in range(1, int(sqrt(n))  + 1,2):# тут я сделал шаг 2
        if n % d == 0:
            ds.append(d)
            if d != n//d:
                ds.append(n//d)
            if len(ds) >= 5:
                break
    if len(ds) ==5:
    	ds.sort()
    	print(n,ds)
[/code]

PEHDOM

Март 31, 2021 12:42:44

Lee У меня дикое дежавю?

     for d in range(1, int(sqrt(n))  + 1,2):# тут я сделал шаг 2

это ошибка, вы должны перебирать все делители если берете от 1 до корня из n потому что при делении на 2 может получиться нечетное число, тоесть 2 не подходит а вот второе числ вполне себе. и вы должны проверять каждый делитель на четность в таком случае. У вас вообще проверки на четность нет.

Lee
Нужно вывести все числа которые имеют ровно 5 различных нечетных делителя

Если подразумевается что число должно иметь ровно 5 нечетных и 0 четных,тоесть всего 5, то нужно вспомнить что неченое количество делителей будет только если число имеет целочисленный корень.

Lee

Март 31, 2021 13:08:04

Количество честных делителей может быть любым
Имеется ввиду, только те числа которые имеют 5 нечетных делителя
Даже если отсеить 1, то остаётся еще 4 элемента. Я сделал проверку от 2 до корня из числа + в условии if добавил, что число d не делится на 2. Но все равно, программа долго работает(
Я еще думал сделать 2 цикла. Первый, если число четное, значит нужно найти еще 4 нечетных делителя. И второй если число нечётное, значит нужно найти ещё 3 нечетных делителя. Но он вообше не работал
Так что сейчас мой максимум, это вот это

[code python]from math import sqrt
a = 45000000
b = 50000000
k=0
for n in range(a, b + 1):
    ds = []
    for d in range(1, int(sqrt(n))  + 1):
        if n % d == 0 and d%2!=0:
            ds.append(d)
            if d != n//d:
                ds.append(n//d)
            if len(ds) >= 5:
                break
    if len(ds) ==5:
    	ds.sort()
    	print(n,ds) [/code]

PEHDOM

Апрель 1, 2021 14:03:17

Lee
Но все равно, программа долго работает

ну так, перебрать пять миллионов чисел и для каждого проверить делиться ли оно нацело на 1- 7000 тупо перебором оно будет долго.
Мне, честно говоря, не приходит в голову как ускорить это процесс, так как никаких признаков (что число имеет более/менее/ровно 5-ти нечетных делителей и любое количество четных) чтобы отбросить часть чисел я не вижу.
Перебор одного миллиона занимает примерно 10 минут, а у вас 5 миллионов.

Чисто эмпирически , запустив таки перебор, выяснилось что все “числа которые имеют ровно 5 различных нечетных делителя и любое колличество четных” имеют целочисленный корень, но подвести теорию под это, я не могу.