Форум программистов, компьютерный форум, киберфорум
Python для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.69/140: Рейтинг темы: голосов - 140, средняя оценка - 4.69
0 / 0 / 0
Регистрация: 20.05.2019
Сообщений: 2

Проект Эйлера. Задача 5

20.05.2019, 23:07. Показов 28093. Ответов 10

Студворк — интернет-сервис помощи студентам
День добрый!

Решаю пятую задачу Проекта Эйлера:

"2520 - самое маленькое число, которое делится без остатка на все числа от 1 до 10.
Какое самое маленькое число делится нацело на все числа от 1 до 20?"

Написан следующий код:

Python
1
2
3
4
5
6
7
8
9
10
A = list (range (1 , 21 , 1))
i = 1
 
while i < 100000000 :
    if all (i % it == 0 for it in A) :
        print (i)
        i +=1
        continue   
    else :
        i+=1
Для выполнения условий для чисел от 1 до десяти он работает. При ограничении while до 10'000, для чисел от 1 до 20, при ограничении while до 500'000'000 - Time limit exceeded.

Решение у данной задачи 200 с лишним миллионов. Не зная этого , в любом случае, необходимо перебрать все числа, пока не получим искомое. Т.е. необходим цикл поиска на 200 с лишним миллионов итераций.

Нашел в интернете другой вариант решения, но он так же превышает лимит времени.

Python
1
2
3
4
5
6
7
8
9
10
11
a=1
i=2
 
while i!=20:
  if a%i==0:
     i+=1
  else: 
    i=1
    a+=1
 
print (a)
И любой такой цикл будет превышать лимит времени, или есть какое-то отличное от такого способа перебора решение?
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
20.05.2019, 23:07
Ответы с готовыми решениями:

Проект Эйлера задача 18
Нужно начиная в вершине треугольника и перемещаясь вниз на смежные числа,так максимальная сумма до основания составляет 23. 3 7 4 2 4...

Проект Эйлера задача 15
Начиная в левом верхнем углу сетки 2×2 и имея возможность двигаться только вниз или вправо, существует ровно 6 маршрутов до правого нижнего...

Проект Эйлера задача 18, оптимизация
Решил задачу Эйлера # № 18 через brute force, теперь хочу её уменьшить рекурсией но не могу понять как это можно сделать! Только затронул...

10
 Аватар для m0nte-cr1st0
1043 / 578 / 242
Регистрация: 15.01.2019
Сообщений: 2,178
Записей в блоге: 1
21.05.2019, 10:24
Grigoriy_Gavr, https://docs.python.org/3/libr... l#math.gcd
1
1732 / 970 / 199
Регистрация: 22.02.2018
Сообщений: 2,693
Записей в блоге: 6
21.05.2019, 13:28
m0nte-cr1st0, Извините, я что то не врублюсь. Как здесь использовать наибольший общий делитель? Для каких чисел его искать?

Добавлено через 22 минуты
Grigoriy_Gavr, Нашел информацию, но ссылка почему то не копируется.
Скопировал содержимое и преобразовал, что бы не искажалось.
"""Задачу можно решить и без перебора.
Для начала, берёте все числа от 2 до 20 и раскладываете на простые множители.
Как-то так:
2 = 2^1
3 = 3^1
4 = 2^2
5 = 5^1
6 = 2^1·3^1
7 = 7^1
8 = 2^3
9 = 3^2
10 = 2^1·5^1
11 = 11^1
12 = 2^2·3^1
13 = 13^1
14 = 2^1·7^1
15 = 3^1·5^1
16 = 2^4
17 = 17^1
18 = 2^1·3^2
19 = 19^1
20 = 2^2·5^1
Затем берёте максимальные степени из всех разложений и перемножаете их:
2^4·3^2·5^1·7^1·11^1·13^1·17^1·19^1 = 232792560
"""
1
Эксперт Pascal/Delphi
 Аватар для droider
4888 / 2822 / 865
Регистрация: 04.10.2012
Сообщений: 10,264
21.05.2019, 14:11
Grigoriy_Gavr, для решения этой задачи необходимо найти наименьшее общее кратное (НОК) чисел от 1 до 20 (в англ. версии lcm(a, b) - least common multiple).

решение 1.

Python
1
2
3
4
5
6
7
8
9
10
11
12
from fractions import gcd
 
# та самая функция
 
def lcm(a, b):
    return a / gcd(a, b) * b
 
res = 1
for i in range(2, 20):
    res = lcm(res, i)
 
print('Это число', res)
решение 2.

Python
1
2
3
4
from fractions import gcd
from functools import reduce
 
print('Это число', reduce(lambda a, b: (a * b) /gcd(a, b), range(1, 20), 1))
Code
1
2
Это число 232792560.0
>>>
P.S. почитайте про вычисление НОК для понимания алгоритма.

Добавлено через 1 минуту
Цитата Сообщение от Viktorrus Посмотреть сообщение
Как здесь использовать наибольший общий делитель?
см. выше
2
0 / 0 / 0
Регистрация: 20.05.2019
Сообщений: 2
21.05.2019, 14:27  [ТС]
Огромное спасибо всем ответившим. Буду разбираться.
0
0 / 0 / 0
Регистрация: 05.08.2019
Сообщений: 1
05.08.2019, 21:59
Вот что получилось у меня:
Python
1
2
3
4
5
6
7
8
9
10
n=20
i=19
while i>0:
  if n%i==0: 
      i-=1
  else:
      n+=20
      i=19
  if i==1:  
    print (n)
Ответ: 232792560
0
Эксперт PythonЭксперт Java
19530 / 11067 / 2931
Регистрация: 21.10.2017
Сообщений: 23,294
06.08.2019, 06:55
Цитата Сообщение от Viktorrus
что бы не искажалось.
Тег NOPARSE
0
0 / 0 / 0
Регистрация: 28.01.2020
Сообщений: 1
28.01.2020, 01:21
Python
1
2
3
4
5
6
7
8
9
c = 0
e = 0
while c != 20:
    c = 0
    e += 2520
    for i in range(1,21):
        if e % i == 0:
            c += 1
print(e)
Добавлено через 9 минут
просто и быстро

Добавлено через 2 минуты
берем число 2520 и его плюсуем каждый проход цикла
Ответ: 232792560
0
0 / 0 / 0
Регистрация: 19.01.2020
Сообщений: 41
28.01.2020, 08:36
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a
    
def lcm(a, b):
    return a * b / gcd(a, b)
 
def lcmList(nums):
    if (len(nums) == 2):
        return int(lcm(nums[0], nums[1]))
    last = nums.pop()
    return int(lcm(lcmList(nums), last))
  
nums = []  
for i in range(1, 21):
    nums.append(i)
    
print(lcmList(nums))
0
0 / 0 / 0
Регистрация: 14.12.2020
Сообщений: 1
14.12.2020, 12:43
Находим значение для любого n.
Изначально находим произведение и убираем ненужные множители.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
n = 20
arr=list(range(1,n+1))
num=1
for j in arr:
    num*=j
 
numbers=[]
for i in arr[::-1]:
    num=num/i
    for j in arr[::-1]:
        if num%j!=0:
            num=num*i
            break
        else:
            continue
    numbers.append(int(num))
print(min(numbers))
0
0 / 0 / 0
Регистрация: 24.10.2019
Сообщений: 1
23.03.2021, 09:15
Начал решать задачи Эйлера, таким получился мой вариант
Python
1
2
3
4
5
6
7
8
9
10
11
12
k=20
mn=6
for n in range(4,k+1):
    i=2
    while mn%n!=0:
        if n%i==0:
            while n>i:
                n=n/i
            mn*=n
        else:
            i+=1
print(mn)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
23.03.2021, 09:15
Помогаю со студенческими работами здесь

Проект Эйлера Задача 11, работа с таблицами вроде как:)
Привет, я новенький в питоне, наткнулся на проект Эйлера, задача номер 11(https://euler.jakumo.org/problems/view/11.html) все вроде как...

Проект Эйлера, задача №7. Какое число является 10001-ым простым числом?
Доброго времени суток. Я начинающий питонер\питонист\питонщик\ набрасал такой вот кодец. Прошу вашего мнения. Может кому пригодится. За...

Проект Эйлера
Я только недавно начал учить питон(это мой первый язык программирования), я пробовал свои силы в проекте Эйлера, первую задачу более менее...

Проект Эйлера, прыгающие числа
Прыгучие числа Если, читая число слева направо, ни одна цифра не превышает цифру справа от нее, то такое число называется...

Проект Эйлера: Наибольшее произведение в последовательности
Добрый вечер всем, решал задачу из проекта Эйлера, вот условие: https://euler.jakumo.org/problems/view/8.html Так как число, слишком...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Новые блоги и статьи
Знаешь почему 90% людей редко бывают счастливыми?
kumehtar 14.04.2026
Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.
Фиксация колонок в отчете СКД
Maks 14.04.2026
Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .
Настройки VS Code
Loafer 13.04.2026
{ "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .
Оптимизация кода на разграничение прав доступа к элементам формы
Maks 13.04.2026
Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .
Контроль заполнения и очистка дат в зависимости от значения перечислений
Maks 12.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .
Архитектура слоя интернета для сервера-слоя.
Hrethgir 11.04.2026
В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .
Подстановка значения реквизита справочника в табличную часть документа
Maks 10.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача №1: при указании работ (справочник РаботыПоРемонтуСпецтехники),. . .
Очистка реквизитов документа при копировании
Maks 09.04.2026
Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru