Как найти нок в питоне

Ускорение нахождения НОК двух чисел

Я написал код для нахождения НОК заданных чисел, но он не вписывается в рамки времени. Подскажите пожалуйста как его ускорить.

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 сек.
Отслеживать
48.6k 17 17 золотых знаков 56 56 серебряных знаков 100 100 бронзовых знаков
задан 8 июн 2020 в 9:41
37 1 1 золотой знак 1 1 серебряный знак 14 14 бронзовых знаков
Приложите пример входных данных
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.7k 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
181 2 2 серебряных знака 23 23 бронзовых знака

python
python-3.x

Важное на Мете

Подписаться на ленту

Лента вопроса

Для подписки на ленту скопируйте и вставьте эту ссылку в вашу программу для чтения RSS.

Нажимая «Принять все файлы cookie» вы соглашаетесь, что Stack Exchange может хранить файлы cookie на вашем устройстве и раскрывать информацию в соответствии с нашей Политикой в отношении файлов cookie.

Нахождение НОК и НОД в Python — примеры

В данном уроке мы узнаем, как найти наименьшее общее кратное (НОК) и наибольший общий делитель (НОД) с помощью языка программирования Python.

Но прежде чем мы начнем, давайте разберем, что обозначает Least Common Multiple (LCM) — наименьшее общее кратное.

НОК: наименьшее общее кратное

Это понятие арифметики и системы счисления. НОК двух целых чисел a и b обозначается НОК(a,b). Это наименьшее натуральное число, которое делится и на «а», и на «b».

Например: у нас есть два целых числа 4 и 6. Найдем НОК:

4, 8, 12, 16, 20, 24, 28, 32, 36. and so on.

Кратные 6:

6, 12, 18, 24, 30, 36, 42. and so on.

Общие кратные 4 и 6 — это просто числа, которые есть в обоих списках:

12, 24, 36, 48, 60, 72. and so on.

НОК — это наименьший общий множитель, поэтому он равен 12.

Поскольку мы поняли основную концепцию НОК, давайте рассмотрим следующую программу для нахождения НОК заданных целых чисел.

# defining a function to calculate LCM def calculate_lcm(x, y): # selecting the greater number if x > y: greater = x else: greater = y while(True): if((greater % x == 0) and(greater % y == 0)): lcm = greater break greater += 1 return lcm # taking input from users num1 = int(input("Enter first number: ")) num2 = int(input("Enter second number: ")) # printing the result for the users print("The L.C.M. of", num1,"and", num2,"is", calculate_lcm(num1, num2))

Enter first number: 3 Enter second number: 4 The L.C.M. of 3 and 4 is 12

Эта программа сохраняет два числа в num1 и num2 соответственно. Эти числа передаются в функцию calculate_lcm(). Функция возвращает НОК двух чисел.

Внутри функции мы сначала определили большее из двух чисел, поскольку наименьшее общее кратное может быть больше или равно наибольшему числу. Затем мы используем бесконечный цикл while, чтобы перейти от этого числа и дальше.

На каждой итерации мы проверяли, идеально ли делят оба числа число. Если это так, мы сохранили число как НОК и вышли из цикла. В противном случае число увеличивается на 1, и цикл продолжается.

НОД: наибольший общий делитель

В этом разделе мы разберем, как найти Highest Common Factor (HCF) — наибольший общий делитель (НОД) в языке программирования Python.

Наибольший общий делитель двух или более целых чисел, когда хотя бы одно из них не равно нулю, является наибольшим положительным целым числом, которое без остатка делит целые числа. Например, НОД 8 и 12 равен 4.

У нас есть два целых числа 8 и 12. Найдем наибольший общий делитель.

Делители числа 8:

1, 2, 4, 8

Делители числа 12:

1, 2, 3, 4, 6, 12

НОД 8 и 12 равны 4.

Теперь давайте рассмотрим пример, основанный на нахождении НОД двух заданных чисел.

# defining a function to calculate HCF def calculate_hcf(x, y): # selecting the smaller number if x > y: smaller = y else: smaller = x for i in range(1,smaller + 1): if((x % i == 0) and(y % i == 0)): hcf = i return hcf # taking input from users num1 = int(input("Enter first number: ")) num2 = int(input("Enter second number: ")) # printing the result for the users print("The H.C.F. of", num1,"and", num2,"is", calculate_hcf(num1, num2))

Enter first number: 8 Enter second number: 12 The H.C.F. of 8 and 12 is 4

В приведенном выше фрагменте кода два целых числа, хранящиеся в переменных num1 и num2, передаются в функцию calculate_hcf(). Функция вычисляет НОД для этих двух чисел и возвращает его.

Внутри функции мы должны определить меньшее число, поскольку НОД может быть меньше или равен наименьшему числу. Затем мы использовали цикл for, чтобы перейти от 1 к этому числу.

На каждой итерации мы должны проверять, точно ли число делит оба входных числа. Если это так, мы должны сохранить число как НОД. По завершении цикла мы получаем наибольшее число, которое идеально делит оба числа.

Наименьшее общее кратное

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

# Наименьшее общее кратное двух чисел - # это наименьшее число, # которое делится нацело на оба заданных числа. def lcm(a, b): # Произведение всегда кратно # любому из своих множителей. m = a * b # Однако оно может быть # не наименьшим общим кратным. # поиск наибольшего общего делителя while a != 0 and b != 0: if a > b: a = a % b else: b = b % a # Наименьшее общее кратное вычисляется # с помощью деления произведения чисел # на их наибольший общий делитель. # Здесь используется целочисленное деление # только потому, что Python # при обычном делении (/) # всегда возвращает тип float. return m // (a + b) x = int(input('a=')) y = int(input('b=')) print('LCM:', lcm(x, y))