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

@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 то откуда?

Новые блоги и статьи Все статьи Все блоги /
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .

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

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

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

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

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

@Gdez 8840 / 4492 / 1864 Регистрация: 27.03.2020 Сообщений: 7,312
	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