Оптимизация программы для задачи

@GavNoKoder · Регистрация: 18.03.2018

Студворк — интернет-сервис помощи студентам

Есть задача:

На промежутке [106 000 001; 107 000 000] найти количество чисел, которые имеют ровно 3 различных четных делителя

Написать программу несложно, но она не компилируется, ибо числа очень большие. Объясните как ее сделать, пожалуйста.

@Arsegg · 05.02.2021, 18:08

Сообщение от GavNoKoder

Написать программу несложно, но она не компилируется, ибо числа очень большие.

Это шутка? Код в студию!

@GavNoKoder · 05.02.2021, 18:14 **[ТС]**

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
count = 0
for i in range(106000001, 107000001):
    if i % 2 != 0:
        continue
    divers = 0
    for k in range(2, i+1):
        if k % 2 == 0 and i % k == 0:
            divers += 1
            if divers > 3:
                break
    if divers == 3:
        count += 1
print(count)

@Arsegg · 05.02.2021, 18:25

GavNoKoder, ну дак надо писать нормальный алгоритм на количество делителей за O(sqrt(n)), а не за линию, как сейчас у тебя написано..
/upd

Сообщение от GavNoKoder

имеют ровно 3 различных четных делителя

И не совсем ясное условие: ровно 3 различных среди четных делителей или 3 различных четных среди всех...

@Gdez · 05.02.2021, 18:42

GavNoKoder,

Python
1
2
3
4
5
6
7
8
9
10
11
def isPrime(n):
    d = 3
    while d * d <= n and n % d != 0:
        d += 2
    return d * d > n 
    
    
if __name__ in '__main__' :
    
    res = sum(1 for i in range(7281, 9221, 2) if isPrime(i))
    print(res)

Добавлено через 2 минуты
Только три различных четных делителя имеют числа, при делении на 2 которые являются квадратами простых чисел.
18 = 2*3*3 -> 1, 2, 3, 6, 9, 18
50 = 2*5*5 -> 1, 2, 5, 10, 25, 50
...

@Gdez · 05.02.2021, 18:44

Это не на программирование, а на математику

@GavNoKoder · 05.02.2021, 18:50 **[ТС]**

А как до этого можно было додуматься?)

@Gdez · 05.02.2021, 19:08

GavNoKoder, только квадраты чисел имеют нечетное число делителей. Если в задаче условие на четность, то один из делителей 2. Квадрат простого числа имеет ровно три делителя, умноженные на 2 дадут ровно три четных делителя -> делители 1, р, р^2 -> *2 -> 2, 2р, 2р^2 плюс 1, р, р^2

Добавлено через 12 минут
GavNoKoder, GavNoKoder, ошибка - считал до 170 млн :
Диапазон - range(7281, 7315, 2)

Новые блоги и статьи Все статьи Все блоги /
Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .	Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .	Команды формы и диалоговое окно Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .
Кому нужен AOT? DevAlt 26.03.2026 Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .	Отправка уведомления на почту при изменении наименования справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере изменения наименования типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной. . .	модель ЗдравоСохранения 5. Меньше увольнений- больше дохода! anaschu 24.03.2026 Теперь система здравосохранения уменьшает количество увольнений. 9TO2GP2bpX4 a42b81fb172ffc12ca589c7898261ccb/ https:/ / rutube. ru/ video/ a42b81fb172ffc12ca589c7898261ccb/ Слева синяя линия -. . .	Midnight Chicago Blues kumehtar 24.03.2026 Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .

@GavNoKoder 0 / 0 / 0 Регистрация: 18.03.2018 Сообщений: 61

	Оптимизация программы для задачи 05.02.2021, 18:01. Показов 2577. Ответов 7 Метки нет (Все метки) Есть задача: На промежутке [106 000 001; 107 000 000] найти количество чисел, которые имеют ровно 3 различных четных делителя Написать программу несложно, но она не компилируется, ибо числа очень большие. Объясните как ее сделать, пожалуйста. 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,317
	05.02.2021, 18:44
	Это не на программирование, а на математику 0

@GavNoKoder 0 / 0 / 0 Регистрация: 18.03.2018 Сообщений: 61
	05.02.2021, 18:50 [ТС]
	А как до этого можно было додуматься?) 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,317
	05.02.2021, 19:08
	GavNoKoder, только квадраты чисел имеют нечетное число делителей. Если в задаче условие на четность, то один из делителей 2. Квадрат простого числа имеет ровно три делителя, умноженные на 2 дадут ровно три четных делителя -> делители 1, р, р^2 -> 2 -> 2, 2р, 2р^2 плюс 1, р, р^2 Добавлено через 12 минут* GavNoKoder, GavNoKoder, ошибка - считал до 170 млн : Диапазон - range(7281, 7315, 2) 2

Оптимизация программы для задачи

Решение