Repository navigation
Expand file tree
/
Copy path005-smallest-multiple.py
More file actions
executable file
·50 lines (45 loc) · 3.79 KB
/
Copy path005-smallest-multiple.py
File metadata and controls
executable file
·50 lines (45 loc) · 3.79 KB
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
#!/usr/bin/python3
"""
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
"""
# This code runs in 6.89029693604e-05 seconds.
import time
# This function finds the prime factors of an integer, n.
def prime_factors(n): # Accepts an integer, n, of which prime factors are found.
i = 2 # Sets our prime factor to 2.
factors = [] # Creating a list which will hold the prime factors.
while n >= i: # While our number is greater than or equal to our prime factor,
while n % i == 0: # While the number is evenly divisible by our prime factor,
factors.append(i) # Add the factor to our list.
n = n / i # Cut down our number by dividing out the factor.
if i == 2: # If our prime factor is 2,
i += 1 # Add one.
else: # Otherwise,
i += 2 # Add two (all subsequent prime factors are odd).
return factors # Return the list of the prime factors.
# This problem is solved by constructing the number by multiplying together the uncommon prime numbers and excluding any repeats not in the same group.
# Example: The prime factors of 2520 are 2, 2, 2, 3, 3, 5, and 7. Now we look at the prime factors for numbers 10 through 1:
# 10 = 2 * 5, 9 = 3 * 3, 8 = 2 * 2 * 2, 7 = 7, 6 = 2 * 3, 5 = 5, 4 = 2 * 2, 3 = 3, 2 = 2, and 1 = 1
# If we take the five from the 10, the two threes from the nine, the three twos from 8, and the seven from 7,
# All of the prime factors in this group are accounted for, and there are only as many of them as there are in one group
# (three two's from 8 and two three's from 9). When we multiply all these factors, we get 2520, the smallest, evenly divisible number.
# This function finds the smallest number that is evenly divisible by all the numbers between 1 and an integer, n.
def evenly_divisible(n): # Accepts an integer, n, which serves as the upper bound for divisible range.
factors = [] # Empty list to hold the prime factors we need to make our evenly divisible number.
while n > 1: # While the upper bound is greater than one,
primes = prime_factors(n) # Import all of the prime factors for the upper bound.
for i in primes: # Iterate through all of the prime factors for the upper bound.
if primes.count(i) > factors.count(i): # If # of a specific factor is greater than the # of that factor we have stored,
for j in range(0, primes.count(i) - factors.count(i)): # Repeat the next step the (difference between the counts) times.
factors.append(i) # Store this factor to our factor list.
n -= 1 # Decrement our number by 1.
product = 1 # Create a variable which will store our product.
for k in factors: # Iterate through the list of factors we've compiled.
product *= k # Multiply the product by the current factor.
return product # Return the product
#print evenly_divisible(10)
s = time.time()
print(evenly_divisible(20))
f = time.time()
print(f - s)