I was trying to solve Project Euler Question 5:
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
I have solved this problem and my question isn't really about this problem, but about something I noticed while trying to solve it.
Initially, for each whole number above 20, I thought of checking whether it is divisible by every number from 2 to 20. But every number that is divisible by 20 is also divisible by each of its factors. For example, 100 is divisible by 20 and therefore it is also divisible by 2, 4, 5 and 10. So I tried to make a list of numbers from 1 to 20 such that I only have to check if a number is divisble by numbers from that list. Here's my code for it.
def divisors(n): ''' ''' sieve = [True] * (n + 1) for i in range(n, 2, -1): if sieve[i]: for t in range(2, i // 2 + 1): if i % t == 0: sieve[t] = False return ([i for i in range(2, n + 1) if sieve[i]])
What struck me was that for any value of n, the list of numbers does not change after I have excluded the factors of numbers greater than about 2/3 * n. So for n = 1000, after I have checked all the numbers from 1000 to 667, I don't need to check for factors of any smaller numbers; the list will stay the same regardless. What amazed me even more was that for each n, the final list contained all the numbers for (n/2) + 1 till n. For example, for n = 1000, the final list will be [551, 552, 553, ...... 998, 999, 1000]
I can't figure out why this is true. Can somebody please explain it to me? And I'm not a mathemaician. Please explain it in simple terms.