Наименьшее общее кратное
где a и b — это натуральные числа, НОД — наибольший общий делитель.
Решение задачи на языке программирования Python
Из условия задачи ясно, чтобы найти НОК, надо сначала найти НОД. Последний можно вычислить, постепенно находя остаток от деления большего числа из пары на меньшее и присваивая остаток переменной, связанной с большим числом (см. алгоритм Евклида). В какой-то момент значение одной из переменных станет равным 0. Когда это произойдет, другая будет содержать НОД. Если неизвестно, какая именно переменная содержит НОД, то можно просто сложить значения обоих переменных.
В коде ниже используется функция для нахождения НОК, которая принимает два числа и возвращает найденное наименьшее общее кратное.
В основной ветке программы функция вызывается в цикле, который завершается, если то, что было введено, нельзя преобразовать к целому. В этом случае генерируется исключение и поток выполнения переходит к ветке except .
def lcm(a, b): m = a * b while a != 0 and b != 0: if a > b: a %= b else: b %= a return m // (a + b) while 1: try: x = int(input('a = ')) y = int(input('b = ')) print('НОК:', lcm(x, y)) except ValueError: break
a = 14 b = 18 НОК: 126 a = 105 b = 305 НОК: 6405 a = stop
В модуле math языка программирования Python есть функция для нахождения наибольшего общего делителя ( gcd — greatest common devisor). При ее использовании наша функция вычисления наименьшего общего кратного lcm (least common multiple) упрощается.
def lcm(a, b): import math return (a * b) // math.gcd(a, b)
X Скрыть Наверх
Решение задач на Python
Ускорение нахождения НОК двух чисел
Я написал код для нахождения НОК заданных чисел, но он не вписывается в рамки времени. Подскажите пожалуйста как его ускорить.
b,n=map(int,input().split()) m=max(b,n) while True: if m%b==0 and m%n==0: print(m) break else: m+=1 Время на работу программы 5 сек.
Отслеживать
47.8k 17 17 золотых знаков 56 56 серебряных знаков 100 100 бронзовых знаков
задан 8 июн 2020 в 9:41
27 1 1 золотой знак 1 1 серебряный знак 13 13 бронзовых знаков
Приложите пример входных данных
8 июн 2020 в 9:43
Находит НОК заданных чисел
8 июн 2020 в 9:44
Например Ввод: 14 21. Вывод 42.
8 июн 2020 в 9:45
3 ответа 3
Сортировка: Сброс на вариант по умолчанию
Нашел интересный пример в интернете. Как сказано на вики:
import math n = 14 m = 21 print((n * m) // math.gcd(n , m)) # gcd - greatest common devisor gcd() появился только в Python версии 3.5
Отслеживать
ответ дан 8 июн 2020 в 9:47
13.1k 2 2 золотых знака 21 21 серебряный знак 37 37 бронзовых знаков
Комментарии не предназначены для расширенной дискуссии; разговор перемещён в чат.
8 июн 2020 в 10:44
До python 3.5, в том числе и в 2.7, был fractions.gcd. Есть он и сейчас, но считается устаревшим по отношению к math.gcd
10 июн 2020 в 14:57
После долгой, неплодотворной дискуссии — вот вам решение с нуля.
def gcd(a, b): while b: a, b = b, a % b return a def mcd(n,m): return (n/gcd(n,m))*m print(int(mcd(n,m))) n=14 m=21 n=147 m=214 n=14783678656 m=21456735976 39651186209477312512 Время работы — моментально. Проверяйте.
P.S. math.gcd() реализовано в стандартной библиотеке начиная с версии Python 3.5
Отслеживать
ответ дан 8 июн 2020 в 10:18
11.6k 2 2 золотых знака 10 10 серебряных знаков 16 16 бронзовых знаков
В Python 3.9 добавлена функция для нахождения НОК:
import math print(math.lcm(14, 21)) Также можно воспользоваться numpy :
import numpy as np print(np.lcm(14, 21)) Отслеживать
ответ дан 21 июн 2020 в 8:18
171 2 2 серебряных знака 23 23 бронзовых знака
- python
- python-3.x
-
Важное на Мете
Похожие
Подписаться на ленту
Лента вопроса
Для подписки на ленту скопируйте и вставьте эту ссылку в вашу программу для чтения RSS.
Дизайн сайта / логотип © 2023 Stack Exchange Inc; пользовательские материалы лицензированы в соответствии с CC BY-SA . rev 2023.11.21.1314
Нажимая «Принять все файлы cookie» вы соглашаетесь, что Stack Exchange может хранить файлы cookie на вашем устройстве и раскрывать информацию в соответствии с нашей Политикой в отношении файлов cookie.
Найти НОК нескольких чисел
(60:30 = 2, 60:20 = 3, 60:10 = 6)
60 — это минимальное число, которое можно поделить на эти числа без остатка, проще же — НОК.
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:
Найти НОД и НОК двух чисел
2. Написать функцию, которая находит наибольший общий делитель двух целых чисел, введенных с.
По известным значениям НОД и НОК исходных чисел найти все подходящие пары a и b
Ельцину из параллели C преподаватель дал следующее простое задание: для двух чисел a и b требуется.
Задача: даны НОК и НОД. Нужно найти все пары чисел, для которых они верны. Нужно ускорить код
Коллеги, всем привет. Задача: есть НОК и НОД, нужно найти все пары чисел, для которых они верны. .
Найти НОК
Функция 1. Найти НОК
Найти НОК двух чисел
нужно найти наименьшее общее кратное чисел m и n в чем ошибка?m = int(input(‘m=’)) n =.
6189 / 3426 / 1028
Регистрация: 07.09.2019
Сообщений: 5,490
1 2 3 4 5 6
from math import lcm n = int(input('quantity of numbers')) numbers = [] for i in range(n): numbers.append(int(input('n_'.format(i)))) print(lcm(*numbers))
35356 / 19956 / 4180
Регистрация: 12.02.2012
Сообщений: 33,116
Записей в блоге: 13
DrType, я бы не зачел это решение. И вот почему. Для «решившего» задачу подобным образом, наименьшее общее кратное — это то, что возвращает функция lcm. Что внутри — он может и не знать. А это, на мой взгляд, важно критически. Программист, не знающий алгоритма Евклида — это то же самое, что «инженер», не знающий сопромата.
Регистрация: 19.12.2021
Сообщений: 60
1 2 3 4
Traceback (most recent call last): File "C:/Users/Администратор/PycharmProjects/untitled9/venv/16 01 22 НОК.py", line 1, in module> from math import lcm ImportError: cannot import name 'lcm' from 'math' (unknown location)
что делать, такая ошибка выходит
12739 / 7049 / 1494
Регистрация: 06.09.2009
Сообщений: 26,080
В Python 3.10 прекрасно работает. Но, как сказано выше уважаемым Catstail, можно переделать без привязки к модулю math
Регистрация: 19.12.2021
Сообщений: 60
ого а как переделать
Заяц, просто Заяц.
663 / 277 / 156
Регистрация: 12.11.2017
Сообщений: 873
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
def composition(a): tmp = 1 for i in a: tmp *= i return tmp def lcm(a): for i in range(1, composition(a) + 1): tmp = 0 for j in a: if i % j == 0: tmp += 1 if tmp == len(a): return i a = [int(input('Введите число: ')) for _ in range(int(input('Введите количество чисел: ')))] print(lcm(a))
12739 / 7049 / 1494
Регистрация: 06.09.2009
Сообщений: 26,080
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
def gcd(a, b): if b == 0: return a else: return gcd(b, a%b) def lcm(a, b): return a//gcd(a, b)*b n = int(input('Количество чисел: ')) numbers = [] for i in range(n): numbers.append(int(input('n_: '.format(i)))) res = lcm(numbers[0], numbers[1]) for i in range(2, n): res = lcm(res, numbers[i]) print(res)
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
Помогаю со студенческими работами здесь
Найти пары чисел в последовательности у которых НОД равен НОК
Почему в интерпретаторе работает, а на сайте нет? Дано число n – количество чисел. В следующей.
Найти НОК двух чисел, записанных в файле через запятую
нужно найти НОК двух чисел. Числа записаны в файле через запятую,
Найти НОК 3-х чисел, при этом используя метод разбиения на простые множители
Необходимо найти НОК 3-х чисел, при этом используя метод разбиения на простые множители. Написал 3.
Нод и Нок двух чисел
пользователь вводит числа х и у нужно найти: наибольшее натуральное число, на которое у и х.
Вычислить НОК двух чисел
Наименьшее общее кратное (НОК) двух натуральных чисел – это наименьшее число, которое делится.
Как найти нок двух чисел питон
Найдите НОК (наименьшее общее кратное) двух натуральных чисел.
Вход . Два натуральных числа a и b (a, b ≤ 2 * 10 9 ).
Выход . Выведите НОК чисел a и b.
Пример входа
Пример выхода
42 24
РЕШЕНИЕ
Наименьшим общим кратным ( НОК ) двух целых чисел a и b называется наименьшее натуральное число, которое делится нацело на a и на b. Например, НОК (2, 3) = 6, НОК (6, 10) = 30.
Для нахождения наименьшего общего кратного воспользуемся формулой:
НОД(a, b) * НОК( a, b) = a * b
НОК(a, b) = a * b / НОД(a, b)
Рассмотрим числа из примера:
НОД(42 , 24) * НОК(42 , 24) = 42 * 24,
НОК(42 , 24) = 42 * 24 / НОД(42 , 24) = 42 * 24 / 6 = 168
Реализуем функци и gcd (наибольший общий делитель) и lcm (наименьшее общее кратное) .
long long gcd( long long a , long long b )
return (! b ) ? a : gcd( b , a % b );
long long lcm( long long a , long long b )
return a / gcd( a , b ) * b ;
Основная часть программы. Читаем входные данные. Вычисляем и выводим ответ.
def gcd(a, b):
if a == 0: return b
if b == 0: return a
if a > b: return gcd(a % b, b)
return gcd(a, b % a)
def lcm(a, b):
return a // gcd(a, b) * b
a, b = map(int, input().split())
print(lcm(a, b))