从1到20之间所有数字能整除的最小正整数是多少？

Question

我的代码哪里出问题了？我运行程序时什么都没有打印出来。我想要打印出一个能被1到20之间所有数字整除的最小数字。

found = False
i = 20
while found==False:
    c = 0    # c checks if the number is the one im looking for
    for x in range(1,21):
        if i%x==0:
            c = c + 1
    if c==20: # if c = 20 then its the number im looking for
        print i
        found = True
    i = i + 1    

Answer 1

在Ruby中，还有一些简单又快速的东西

def compute_lowest_dividing_number number
  for i in 2..(number/2)
    return i if number%i == 0
  end
  number
end

lcm = 1
n = 20
for i in 1..n
  # look ahead appraoch
  next_number = [i+1, n].min
  lcm *= compute_lowest_dividing_number(next_number) if lcm % next_number != 0
end
puts lcm

Answer 2

def is_divisible(n):
    for divisor in range(2, 21):
         if n % divisor != 0:
              return False
         return True


number = 1
while not is_divisible(number):
     number+=1
print(number)

不过，你不需要检查所有的数字从1到20。如果一个数字能被20整除，那它也一定能被2、5和10整除。进一步说，只需要检查从11到20的数字就可以了。还有一个简单的方法是，每次把候选数字加20（number += 20），而不是加1，因为其他的数字都不会被20整除。

其实，你是在寻找从1到20这些数字的最小公倍数，而这个可以通过质因数分解来实现：你把每个1到20之间的数字写成质数的乘积，然后找出每个质数的最大指数，最后把这些结果相乘（可以手动试试，理解一下这个过程）。这样，你要找的数字就是2^4 * 3^2 * 5 * 7 * 11 * 13 * 17 * 19。

Answer 3

我个人的看法（虽然我很喜欢@ondra的解决方案，因为它很优雅）：

from collections import Counter, defaultdict

def primes(n):
    return list(x for x in range(1,n+1) 
        if all(x%y for y in range(2,x)))

primes_20 = primes(20)

def prime_factors(n):
    if n <= 0 or n < 20:
        raise ValueError
    factors = []
    while n > 1:
        for x in primes_20[1:]:
            if not n % x:
                n = n / x
                factors.append(x)
                break
    return factors

max_count = defaultdict(int)

for i in range(2,21):
    factors = prime_factors(i)
    counts = Counter(factors)
    for factor in counts:
        max_count[factor] = max(max_count[factor], counts[factor])

total = 1
for factor, count in max_count.items():
    total *= factor**count

assert any(total%x for x in range(2)) == False
print total

Answer 4

暴力破解：

from itertools import count
for i in count(20):
    if all(map(lambda x: i % x == 0, range(1, 21))):
        print i
        break

非暴力破解：

from itertools import count, takewhile

def primes(n):
    "Generate prime numbers up to n"
    seen = list()
    for i in xrange(2, n + 1):
        if all(map(lambda prime: i % prime, seen)):
            seen.append(i)
            yield i

def smallest(n):
    result = 1
    for prime in primes(n):
        bprime = max(takewhile(lambda x:x<=n, (prime ** c for c in count(1))))
        # we could just take last instead of max()
        result *= bprime
    return result

print smallest(20)

Answer 5

暴力破解这个方法实在是太慢了。你需要找出20以下每个数字的质因数，然后构造一个包含这些质因数的最小数字，这样就能得到答案。

from collections import Counter

primes_below_20 = [2, 3, 5, 7, 11, 13, 17, 19]

def prime_factors(n):
    # Assume n <= 20 
    if n == 1:
        return []
    for prime in primes_below_20:
        if n % prime == 0:
            return [prime] + prime_factors(n / prime)

 primes_needed = Counter()

 for n in range(2, 21):
     primes = Counter(prime_factors(n))
     primes_needed = primes_needed | primes  # | gives the max of existing values

 total = 1
 for prime, amount in primes_needed.items():
     total *= prime ** amount

 print total