Java中的Euler #5项目:卡在程序的末尾

Question

我试图得到最小的正数，它可以被从1到20的所有数字平均除以，但不知怎么的，我被困在了程序的末尾。我的答案是40岁，这是错误的。这是我的代码：

public class Lessons {

    public static void main(String[] args) {
        int n;
        int s = 0;

        for (n = 21; n > 0; n++) 
        {
         for (int m = 1; m <= 20; m++) 
           {
                s = n % m;
            }
            if (s == 0) 
             {
                System.out.println(n);
                break;
            }

        }
    }
}

有什么帮助吗？

Answer 1

实际上，您只需要检查是否是n%20 == 0。这个循环：

for (int m = 1; m <= 20; m++) {
    s = n % m;
}

运行m从1到20，但是您总是覆盖s，在下一次通过循环重新设置它之前，永远不要使用这个值做任何事情。您需要检查循环的每一次迭代的n % m结果，可能如下：

    for (n = 21; n > 0; n++) {
        bool divisibleByAll = true;

        for (int m = 1; m <= 20; m++) {
            s = n % m;

            if(s != 0) {
                divisibleByAll = false;
                break; //don't bother checking the rest
            }
        }

        if (divisibleByAll) {
            System.out.println(n);
            break;
        }

    }

Answer 2

另一种具有蛮力和模数休息的选择-分类

这个问题可以通过简单的通用模rest类特征来解决。查看从1到20之间的数字，将其分为两组，并在它们之间找到一些独特的公共属性。

%1%2%3%4%5%6%7%8%9 10

   we are building division with the same reminder members

1除以所有

2除以4,8 ->>8重要

3除以6,9，但6不均分9-> 6,9

5除以10 ->>10重要

剩下的是6,7,8,9,10，看看是否有任何数字可以用rest 0除以1。

诀窍是，如果2,4,8除以一个数字，比方说16，用同样的提醒，那么我们不需要检查2,4除以16，我们只检查8。

11 12 13 14 15 16 17 18 19

从上面的数字的因子上我们可以做同样的事情，而我们将被留给

11 12 13 14 15 16 17 18 19

注:我们知道最后一个要除数的数字是20，这意味着要么是一个以0结尾的数字，要么是20的一个因子，所以我们构建20的因子，并检查11 12 13 14 15 16 17 18 19是否可以除以，那么我们就完成了。

int start = 20;

    while (start % 11 != 0 || start % 12 != 0 | start % 13 != 0 || start % 14 != 0 || 
            start % 15 != 0 || start % 16 != 0 || start % 17 != 0 || start % 18 != 0 || start % 19 != 0 )
    {
        start += 20;
    }
    System.out.println("The smallest number is: "+start);

同样的想法也适用于我为使问题看起来更小而做的第一个推论。

//可被1到10的所有数字整除的最小数

int a = 10;

    while (a % 6 != 0 || a % 7 != 0 | a % 8 != 0 || a % 9 != 0 )
    {
        a += 10;
    }

System.out.println("The smallest number is: "+a);

//可被1到5的所有数字整除的最小数

int i = 5;                          

    while (i % 3 != 0 || i % 4 != 0)
    {
        i += 5;
    }

System.out.println("The smallest number is: "+ i);

Answer 3

long startTime = System.currentTimeMillis();
        for ( int i = 2520; ; i += 2520 ){
            if (     i % 11 == 0 && 
                     i % 12 == 0 && 
                     i % 13 == 0 && 
                     i % 14 == 0 && 
                     i % 15 == 0 && 
                     i % 16 == 0 && 
                     i % 17 == 0 && 
                     i % 18 == 0 && 
                     i % 19 == 0 && 
                     i % 20 == 0 ){
                long stopTime = System.currentTimeMillis();
                System.out.println("Answer: " + i + "\nIt took "+(stopTime - startTime) + " milliseconds");
                break;
            }
        }

这平均需要1-2毫秒。我知道这是个蹩脚的解决方案，但是它是有效的。