0

我在这里有一个用 C# 编写的代码，可以找到从 1 到 20 的所有数字的最小倍数。但是，我发现它非常低效，因为执行需要一段时间才能产生正确的答案。我想知道我可以采取哪些不同的方法来改进代码。谢谢你。

        public static void SmallestMultiple()
    {
        const ushort ARRAY_SIZE = 21;
        ushort[] array = new ushort[ARRAY_SIZE];
        ushort check = 0;
        for (uint value = 1; value < uint.MaxValue; value++)
        {
            for (ushort j = 1; j < ARRAY_SIZE; j++)
            {
                array[j] = j;
                if (value % array[j] == 0)
                {   
                    check++;
                }
            }
            if (check == 20)
            {
                Console.WriteLine("The value is {0}", value);
            }
            else
            {
                check = 0;
            }
        }
    }
4

6 回答 6

2

由于结果还必须能被 19（最大的素数）整除，直到 20，您可能只能循环遍历 19 的倍数。

这应该以大约 19 倍的速度获得结果。

这是执行此操作的代码：

public static void SmallestMultiple()
{
    const ushort ARRAY_SIZE = 21;
    ushort[] array = new ushort[ARRAY_SIZE];
    ushort check = 0;

    for (uint value = 19; value < uint.MaxValue; value += 19)
    {
        for (ushort j = 1; j < ARRAY_SIZE; j++)
        {
            array[j] = j;
            if (value % array[j] == 0)
            {
                check++;
            }
        }
        if (check == 20)
        {
            Console.WriteLine("The value is {0}", value);
            return;
        }
        else
        {
            check = 0;
        }
    }
}

在我的机器上，这会232792560在 2 秒多一点的时间内找到结果。

更新

另外，请注意初始程序在达到解决方案时并未停止；我添加了一个return声明以使其停止。

于 2013-01-30T08:29:36.423 回答
2

您只是在寻找从 1 到 20 的数字的LCM ：

公式

其中 GCD 可以使用欧几里得算法有效计算。

我不懂 C#，但这个 Python 解决方案应该不难翻译：

def gcd(a, b):
    while b != 0:
       a, b = b, a % b

    return a

def lcm(a, b):
    return (a * b) / gcd(a, b)

numbers = range(1, 20 + 1)

print reduce(numbers, lcm)

它也非常快：

>>> %timeit reduce(lcm, range(1, 20000))
1 loops, best of 3: 258 ms per loop
于 2013-01-30T08:34:11.917 回答
2 
    static void Main(string[] args)
    {
        int[] nums = Enumerable.Range(1, 20).ToArray();
        int lcm = 1;

        for (int i = 0; i < nums.Length; i++)
        {
            lcm = LCM(lcm, nums[i]);
        }
        Console.WriteLine("LCM = {0}", lcm);
    }

    public static int LCM(int value1, int value2)
    {
        int a = Math.Abs(value1);
        int b = Math.Abs(value2);

        // perform division first to avoid potential overflow
        a = checked((a / GCD(a, b)));
        return checked((a * b));
    }

    public static int GCD(int value1, int value2)
    {
        int gcd = 1;     // Greates Common Divisor

        // throw exception if any value=0
        if (value1 == 0 || value2 == 0)
        {
            throw new ArgumentOutOfRangeException();
        }

        // assign absolute values to local vars
        int a = Math.Abs(value1);            // local var1
        int b = Math.Abs(value2);            // local var2

        // if numbers are equal return the first
        if (a == b) { return a; }
            // if var "b" is GCD return "b"
        if (a > b && a % b == 0) { return b; }
            // if var "a" is GCD return "a"
        if (b > a && b % a == 0) { return a; }

        // Euclid algorithm to find GCD (a,b):
        // estimated maximum iterations: 
        // 5* (number of dec digits in smallest number)
        while (b != 0)
        {
            gcd = b;
            b = a % b;
            a = gcd;
        }
        return gcd;
    }
}

资料来源：快速整数算法：最大公约数和最小公约数，.NET 解决方案

于 2013-01-30T08:36:32.770 回答
1

编辑： v2.0 - 主要速度改进

基于 w0lf 的解决方案。更快的解决方案：

public static void SmallestMultiple()
{
    // this is a bit quick and dirty
    //   (not too difficult to change to generate primeProduct dynamically for any range)
    int primeProduct = 2*3*5*7*11*13*17*19;
    for (int value = primeProduct; ; value += primeProduct)
    {
       bool success = true;
        for (int j = 11; j < 21; j++)
        {
            if (value % j != 0)
            {
                success = false;
                break;
            }
        }
        if (success)
        {
            Console.WriteLine("The value is {0}", value);
            break;
        }
    }
}

您不需要检查 1-10，因为如果某物可以被 x 整除（例如 12），那么它可以被 x/n 整除（例如 12/2 = 6）。最小的倍数将始终是所有涉及的素数的乘积的倍数。

没有对 C# 解决方案进行基准测试，但等效的 Java 解决方案在大约 0.0000006 秒内运行。

于 2013-01-30T09:04:08.343 回答
0

好吧，我不确定您到底想在这里完成什么，但是您的外部 for 循环将运行大约 4,294,967,295 次（uint.MaxValue）。所以这需要一些时间...

如果您有办法避免使用 uint.MaxValue - 例如在完成所需的工作后打破循环 - 这将加快速度。

此外，由于您将 array[j] 设置为等于 j ，然后显然不再使用该数组，为什么不这样做：

value % j

代替

value % array[j]
于 2013-01-30T08:30:15.010 回答
0

还使用 W0lf 编写的代码（抱歉，我不能评论你的帖子）我会改进它（只有一点）删除我认为没用的数组..

public static void SmallestMultiple()
{
    const ushort ARRAY_SIZE = 21;
    ushort check = 0;
    for (uint value = 1; value < uint.MaxValue; value++)
    {
        for (ushort j = 1; j < ARRAY_SIZE; j++)
        {
            if (value % j == 0)
            {   
                check++;
            }
        }
        if (check == 20)
        {
            Console.WriteLine("The value is {0}", value);
        }
        else
        {
            check = 0;
        }
    }
}
于 2013-01-30T08:34:09.720 回答