Большие числа

@Aleksogo · Регистрация: 05.11.2020

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

Здравствуйте, я написал программу, но для больших чисел время выполнения больше, чем нужно. Можете, пожалуйста, помочь исправить программу, чтобы время её выполнения было меньше. Заранее спасибо.
Вот программа на Питоне:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
n=int(input())
a=0
d=[]
c=[0]
f=[]
o=0
for i in range(1,n+1):
    for x in range(-n,n+1):
        for y in range(-n,n+1):
            if x<=n:
                if y<=n:
                    if x**2 + y**2==i**2:
                        a+=1 
                        y+=1 
                    else:
                        y+=1 
                else:
                    x+=1 
            else:
                i+=1 
    for j in range(1):
        d.append(a)
    for h in range(1):
        c.append(a)
    f=[d-c for d,c in zip(d,c)]
    o=f.index(max(f))
print(o+1)

@Gdez · 13.11.2020, 21:36

Miryz, А еще у них есть такие же интересные задачи?

Добавлено через 17 секунд
Вопрос без приколов

Добавлено через 3 минуты
А по поводу этой с ответом 192 можно подколоть их - при условии, что все числа целые, они решили квадратуру круга и определили конечность числа "пи"

@eaa · 13.11.2020, 21:40

задача на обычную факторизацию числа. она вообще по другому решается.

@Miryz · 13.11.2020, 21:44

Gdez,

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

18785

почему не 27625?

Добавлено через 1 минуту
факторизация 5*5*5*13*17

Добавлено через 44 секунды
показатели 3, 1, 1

@Gdez · 13.11.2020, 21:47

Miryz, ответ тестировщик выдал или сам нашел?

@Miryz · 13.11.2020, 21:49

Там нет тестировщика, сам нашел

@Gdez · 13.11.2020, 21:52

Miryz, но коды проверять можешь?

Добавлено через 1 минуту
Miryz, попробуй

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
pifpr = [5, 13, 17, 29, 37, 41, 53, 61, 73, 89, 97]
n = int(input())
s = n
i, a = 0, 1
while n - 1 :
    if pifpr[i] <= n :
        a *= pifpr[i]
        n //= pifpr[i]
        i += 1
    else :
        i = 0
# a - искомый радиус
print(a)

@Miryz · 13.11.2020, 21:52

Если принять что для промежутка до 325, радиус с большим кол-вом точек на окружности 325. Как на этом же промежутке у числа 325 наибольшее кол-во способов составления из суммы квадратов

Добавлено через 22 секунды
Gdez, ты полностью уверен в своей правоте?

@Gdez · 13.11.2020, 21:55

Miryz, 325 вроде включительно

Добавлено через 39 секунд
Miryz,

Gdez, ты полностью уверен в своей правоте?

Там штрафы за попытки?

@Miryz · 13.11.2020, 21:57

Кол-во способов составления числа 27625 - 8, а числа 18785 - 6

Добавлено через 20 секунд
Gdez, хуже, там нет попыток

Добавлено через 1 минуту

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

Кол-во способов составления числа 27625 - 8, а числа 18785 - 6

имею смелость заявить, что у радиуса 27625 будет больше точек на окружности

@Gdez · 13.11.2020, 21:59

Miryz, хреново
Я переделал алгоритм - после превышения следующего числа из pifpr остатка от числа - возвращаемся к началу списка

Добавлено через 33 секунды
Miryz, крайний код выдает 27625

Добавлено через 35 секунд
И цикл все таки до n == 1

@Miryz · 13.11.2020, 21:59

Если все так, как я сказал, то мне осталось только сделать перебор показателей

@Gdez · 13.11.2020, 22:01

Miryz, по идее можно запустить код, который в лоб, на ночь. А утром сверить с моим...
По крайней мере будут числа с верными решениями

@Miryz · 13.11.2020, 22:02

Gdez, аххаха, можешь взять мой алгоритм, правда постить я его не буду, пусть сами разбираются

@Gdez · 13.11.2020, 22:03

Как еаа упомянул - здесь только факторизацией. Но не просто по простым числам, а только по тем, которые есть в пифагоровых тройках в качестве числа "с".
Что я и пытаюсь реализовать

@Miryz · 13.11.2020, 22:04

Gdez,

Не по теме:

если хочешь посмотреть мое решение напиши в лс

@Gdez · 13.11.2020, 22:08

Miryz, имеешь в виду разложение по "n" и "m" троек?

Добавлено через 2 минуты
Мне неизвестен более быстрый алгоритм нахождения примитивных троек.
Потом просто умножаем на натуральные числа каждую тройку, пока не превысит заданное число и при условии, что такой тройки не было.
Но для 10^8 все равно оч долго

@Miryz · 13.11.2020, 22:15

Gdez,

Не по теме:

чек лс

@eaa · 13.11.2020, 22:57

простые числа которые дают остаток 1 при делении на 4.
Киньте сюда пяток тестов, для проверки.

такие тесты?

5000 - 108 - 4930
50000 - 324 - 45305
500000 - 540 - 499525
5000000 - 972 - 4987970

1) это n
2) максимальное количество целых точек
3) максимальный радиус

@Miryz · 13.11.2020, 23:20

eaa, 1) 4225 2) 27625 3)160225 4)4005625

@eaa · 13.11.2020, 23:31

4225 то откуда?

Новые блоги и статьи Все статьи Все блоги /
Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .	Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .	Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .
Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .	Программа опроса у.з. расходомера SLS-720F Argus19 02.09.2026 Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .	Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0. Maks 31.08.2026 При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .	Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм anaschu 30.08.2026 Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,320
	13.11.2020, 21:36
	Miryz, А еще у них есть такие же интересные задачи? Добавлено через 17 секунд Вопрос без приколов Добавлено через 3 минуты А по поводу этой с ответом 192 можно подколоть их - при условии, что все числа целые, они решили квадратуру круга и определили конечность числа "пи" 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	13.11.2020, 21:40
	задача на обычную факторизацию числа. она вообще по другому решается. 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,320
	13.11.2020, 21:47
	Miryz, ответ тестировщик выдал или сам нашел? 0

@Miryz 291 / 131 / 58 Регистрация: 24.11.2019 Сообщений: 532
	13.11.2020, 21:49
	Там нет тестировщика, сам нашел 0

@Miryz 291 / 131 / 58 Регистрация: 24.11.2019 Сообщений: 532
	13.11.2020, 21:52
	Если принять что для промежутка до 325, радиус с большим кол-вом точек на окружности 325. Как на этом же промежутке у числа 325 наибольшее кол-во способов составления из суммы квадратов Добавлено через 22 секунды Gdez, ты полностью уверен в своей правоте? 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,320
	13.11.2020, 21:59
	Miryz, хреново Я переделал алгоритм - после превышения следующего числа из pifpr остатка от числа - возвращаемся к началу списка Добавлено через 33 секунды Miryz, крайний код выдает 27625 Добавлено через 35 секунд И цикл все таки до n == 1 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,320
	13.11.2020, 22:01
	Miryz, по идее можно запустить код, который в лоб, на ночь. А утром сверить с моим... По крайней мере будут числа с верными решениями 0

@Miryz 291 / 131 / 58 Регистрация: 24.11.2019 Сообщений: 532
	13.11.2020, 22:02
	Gdez, аххаха, можешь взять мой алгоритм, правда постить я его не буду, пусть сами разбираются 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,320
	13.11.2020, 22:03
	Как еаа упомянул - здесь только факторизацией. Но не просто по простым числам, а только по тем, которые есть в пифагоровых тройках в качестве числа "с". Что я и пытаюсь реализовать 0

@Miryz 291 / 131 / 58 Регистрация: 24.11.2019 Сообщений: 532
	13.11.2020, 22:04
	Gdez, Не по теме: если хочешь посмотреть мое решение напиши в лс 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,320
	13.11.2020, 22:08
	Miryz, имеешь в виду разложение по "n" и "m" троек? Добавлено через 2 минуты Мне неизвестен более быстрый алгоритм нахождения примитивных троек. Потом просто умножаем на натуральные числа каждую тройку, пока не превысит заданное число и при условии, что такой тройки не было. Но для 10^8 все равно оч долго 0

@Miryz 291 / 131 / 58 Регистрация: 24.11.2019 Сообщений: 532
	13.11.2020, 22:15
	Gdez, Не по теме: чек лс 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	13.11.2020, 22:57
	простые числа которые дают остаток 1 при делении на 4. Киньте сюда пяток тестов, для проверки. такие тесты? 5000 - 108 - 4930 50000 - 324 - 45305 500000 - 540 - 499525 5000000 - 972 - 4987970 1) это n 2) максимальное количество целых точек 3) максимальный радиус 0

@Miryz 291 / 131 / 58 Регистрация: 24.11.2019 Сообщений: 532
	13.11.2020, 23:20
	eaa, 1) 4225 2) 27625 3)160225 4)4005625 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	13.11.2020, 23:31
	4225 то откуда? 0