6

我在 Project Euler 中做问题五：“2520 是可以除以 1 到 10 的每个数字而没有任何余数的最小数字。

能被 1 到 20 的所有数整除的最小正数是多少？”

我构建了以下代码，当使用 1 - 10 作为除数时，它找到了正确的值 2520，但是当使用 1 - 20 时，代码似乎永远在继续。同样，我不希望代码只是我所在位置的一两个指针出错了。谢谢

def smallestDiv(n):
    end=False
    while end == False:
        divisors = [x for x in range(1,21)]    # get divisors
        allDivisions = zip(n % i for i in divisors)    # get values for  n % all integers in divisors
        check = all(item[0]  == 0 for item in allDivisions )   # check if all values of n % i are equal to zero
        if check:         # if all values are equal to zero return n
            end = True
            return n
        else:             # else increase n by 1
            n +=1

编辑：

我使用了一些我发现的与 LCM 相关的代码，并使用 reduce 来解决问题：

def lcm(*values):
    values = [value for value in values]
    if values:
        n  = max(values)
        m = n
        values.remove(n)
        while any( n % value for value in values ):
            n +=m
        return n
    return 0

print reduce(lcm, range(1,21))
4

8 回答 8

25

如果问题很难解决，请尝试解决更简单的版本。在这里，如何计算两个数的最小公倍数。如果您阅读过任何数论书籍（或考虑过素因数），您可以使用最大公约数函数（由欧几里得算法实现）来做到这一点。

from fractions import gcd
def lcm(a,b):
    "Calculate the lowest common multiple of two integers a and b"
    return a*b//gcd(a,b)

观察用 Python 的函数lcm(a,b,c) ≡ lcm(lcm(a,b),c)解决你的问题很简单reduce

>>> from functools import reduce
>>> reduce(lcm, range(1,10+1))
2520
>>> reduce(lcm, range(1,20+1))
232792560
于 2013-10-14T13:12:39.553 回答
4

你正在做一个蛮力搜索，所以它可以得到任意长。您应该阅读有关 LCM（最小公倍数）的信息，以便编写有效的解决方案。（我相信是232792560）

于 2013-10-13T18:12:16.797 回答
2 
int gcd(int m, int n)
{
    int t;
    while(n!=0)
    {
        t=n;
        n=m%n;
        m=t;
    }
    return m;
}

#include<stdio.h>
int main()
{
    int i,n;
    int long long lcm=1;
    printf("Enter the range:");
    scanf("%d",&n);
    for (i=1;i<=n;i++)
    {
        lcm = (i*lcm)/gcd(i,lcm);
    }
    printf("smallest multiple : %uL",lcm);

}
于 2014-04-15T06:41:27.207 回答
1

这将为您提供从 1 到 20 的数字中的所有因子：

from collections import Counter

def prime_factors(x):
    def factor_this(x, factor):
        factors = []
        while x % factor == 0:
            x /= factor
            factors.append(factor)
        return x, factors
    x, factors = factor_this(x, 2)
    x, f = factor_this(x, 3)
    factors += f
    i = 5
    while i * i <= x:
        for j in (2, 4):
            x, f = factor_this(x, i)
            factors += f
            i += j
    if x > 1:
        factors.append(x)
    return factors

def factors_in_range(x):
    result = {}
    for i in range(2, x + 1):
        p = prime_factors(i)
        c = Counter(p)
        for k, v in c.items():
            n = result.get(k)
            if n is None or n < v:
                result[k] = v
    return result

print factors_in_range(20)

如果将这些数字相乘，只要它们出现在结果中的次数，就会得到将所有数字从 1 整除到 20 的最小数字。

import operator

def product(c):
    return reduce(operator.__mul__, [k ** v for k, v in c.items()], 1)

c = factors_in_range(20)
print product(c)
于 2013-10-14T12:55:13.547 回答
0 
facList=[2]
prod=1

for i in range(3,1000):
    n=i
    for j in facList:
        if n % j == 0:
            n//=j
    facList.append(n)

for k in facList:
prod*=k

print(prod)

我尝试了这种方法，并将我的时间与 Panic 上校的答案进行了比较，我的时间开始明显超过他的 n=200 而不是 n=20。在我看来，他的优雅得多，但出于某种原因，我的速度更快。也许对算法运行时有更好理解的人可以解释原因。

于 2014-06-22T05:45:26.193 回答
0 
import sys

def smallestDiv(n):
    divisors = [x for x in range(1,(n+1))]    # get divisors
    for i in xrange(2520,sys.maxint,n):
        if(all(i%x == 0 for x in divisors)):
            return i

print (smallestDiv(20))

在我的 1.7 GHZ i7 上大约需要 5 秒

我基于这里的 C# 代码：http: //www.mathblog.dk/project-euler-problem-5/

于 2013-10-13T18:18:10.567 回答
0

I think the answer by Colonel Panic is brilliant but I just wanted to expand on it a little bit without editing the concise answer.

The original solution is:

from fractions import gcd
def lcm(a,b):
    "Calculate the lowest common multiple of two integers a and b"
    return a*b//gcd(a,b)

>>> from functools import reduce
>>> reduce(lcm, range(1,10+1))
2520
>>> reduce(lcm, range(1,20+1))
232792560

I find it helpful to visualize what the reduce is doing for N = 10: 

res = lcm(lcm(lcm(lcm(lcm(lcm(lcm(lcm(lcm(1, 2), 3), 4), 5), 6), 7), 8), 9), 10)

Which evaluates to:

# Evaluates lcm(1, 2)
res = lcm(lcm(lcm(lcm(lcm(lcm(lcm(lcm(lcm(1, 2), 3), 4), 5), 6), 7), 8), 9), 10)
# Evaluates lcm(2, 3)
res = lcm(lcm(lcm(lcm(lcm(lcm(lcm(lcm(2, 3), 4), 5), 6), 7), 8), 9), 10)
# Evaluates lcm(6, 4)
res = lcm(lcm(lcm(lcm(lcm(lcm(lcm(6, 4), 5), 6), 7), 8), 9), 10)
# Evaluates lcm(12, 5)
res = lcm(lcm(lcm(lcm(lcm(lcm(12, 5), 6), 7), 8), 9), 10)
# Evaluates lcm(60, 6)
res = lcm(lcm(lcm(lcm(lcm(60, 6), 7), 8), 9), 10)
# Evaluates lcm(60, 7)
res = lcm(lcm(lcm(lcm(60, 7), 8), 9), 10)
# Evaluates lcm(420, 8)
res = lcm(lcm(lcm(420, 8), 9), 10)
# Evaluates lcm(840, 9)
res = lcm(lcm(840, 9), 10)
# Evaluates lcm(2520, 10)
res = lcm(2520, 10)

print(res)
>>> 2520

The above gets across the intuition of what is happening. When we use reduce we "apply a rolling computation to sequential pairs of values in a list." It does this from the "inside-out" or from the left to the right in range(1, 20+1).

I think it is really important here to point out that you, as a programmer, are NOT expected to intuit this answer as being obvious or readily apparent. It has taken a lot of smart people a long time to learn a great deal about prime numbers, greatest common factors, and least common multiples, etc. However, as a software engineer you ARE expected to know the basics about number theory, gcd, lcm, prime numbers, and how to solve problems with these in your toolkit. Again, you are not expected to re-invent the wheel or re-discover things from number theory each time you solve a problem, but as you go about your business you should be adding tools to your problem solving toolkit.

于 2019-06-03T13:02:15.147 回答
0

最后一个函数找到可被 n 整除的最小数字，因为该数字应该是阶乘（n）的倍数，所以您需要一个计算阶乘的函数（可以通过数学方法完成）

def factoral(n):
    if n > 1:
        return n * factoral(n - 1)
    elif n >= 0:
        return 1
    else:
        return -1

def isMultiple(a, b):
    for i in range(1, b):
        if a % i != 0:
            return False
    return True

def EnkucukBul(n):
    for i in range(n, factoral(n) + 1, n):
        if isMultiple(i, n):
            return i
    return -1
于 2019-02-21T14:39:32.487 回答