GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — Python-1/maths/least_common_multiple.py at master · https-github-com-nzysoft/Python-1

Expand file tree

/

least_common_multiple.py

Copy path
More file actions
More file actions

Latest commit

 

History

History
History
94 lines (79 loc) · 2.59 KB
/

least_common_multiple.py

Copy path

File metadata and controls

94 lines (79 loc) · 2.59 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
import unittest
from timeit import timeit
def least_common_multiple_slow(first_num: int, second_num: int) -> int:
"""
Find the least common multiple of two numbers.
Learn more: https://en.wikipedia.org/wiki/Least_common_multiple
>>> least_common_multiple_slow(5, 2)
10
>>> least_common_multiple_slow(12, 76)
228
"""
max_num = first_num if first_num >= second_num else second_num
common_mult = max_num
while (common_mult % first_num > 0) or (common_mult % second_num > 0):
common_mult += max_num
return common_mult
def greatest_common_divisor(a: int, b: int) -> int:
"""
Calculate Greatest Common Divisor (GCD).
see greatest_common_divisor.py
>>> greatest_common_divisor(24, 40)
8
>>> greatest_common_divisor(1, 1)
1
>>> greatest_common_divisor(1, 800)
1
>>> greatest_common_divisor(11, 37)
1
>>> greatest_common_divisor(3, 5)
1
>>> greatest_common_divisor(16, 4)
4
"""
return b if a == 0 else greatest_common_divisor(b % a, a)
def least_common_multiple_fast(first_num: int, second_num: int) -> int:
"""
Find the least common multiple of two numbers.
https://en.wikipedia.org/wiki/Least_common_multiple#Using_the_greatest_common_divisor
>>> least_common_multiple_fast(5,2)
10
>>> least_common_multiple_fast(12,76)
228
"""
return first_num // greatest_common_divisor(first_num, second_num) * second_num
def benchmark():
setup = (
"from __main__ import least_common_multiple_slow, least_common_multiple_fast"
)
print(
"least_common_multiple_slow():",
timeit("least_common_multiple_slow(1000, 999)", setup=setup),
)
print(
"least_common_multiple_fast():",
timeit("least_common_multiple_fast(1000, 999)", setup=setup),
)
class TestLeastCommonMultiple(unittest.TestCase):
test_inputs = [
(10, 20),
(13, 15),
(4, 31),
(10, 42),
(43, 34),
(5, 12),
(12, 25),
(10, 25),
(6, 9),
]
expected_results = [20, 195, 124, 210, 1462, 60, 300, 50, 18]
def test_lcm_function(self):
for i, (first_num, second_num) in enumerate(self.test_inputs):
slow_result = least_common_multiple_slow(first_num, second_num)
fast_result = least_common_multiple_fast(first_num, second_num)
with self.subTest(i=i):
self.assertEqual(slow_result, self.expected_results[i])
self.assertEqual(fast_result, self.expected_results[i])
if __name__ == "__main__":
benchmark()
unittest.main()
You are visitor 01402520 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.