1

问题 5： 2520 是可以除以 1 到 10 的每个数字而没有任何余数的最小数字。能被 1 到 20 的所有数整除的最小正数是多少？

我已经解决了Project Euler的问题 5

这是Java代码：

 static long FindLcm(long a,long b)
 {
     long lcm,hcf = 0;
     long i=1;
     long ger=a>b?a:b;
     while(i<ger)
     {
         if((a%i==0) && (b%i==0))
             hcf=i;
         i++;
     }
     lcm=(a*b)/hcf;
     return lcm;
 }
 static void FindMultiple()
 {
     long lcm=1;
     for(long i=2;i<=20;i++)
     {
         lcm=FindLcm(lcm,i);
     }   
     System.out.println("Lcm="+lcm);
 }

如何优化这个？

4

10 回答 10

6

你的FindMultiple()方法还不错，

static void FindMultiple()
{
    long lcm=1;
    for(long i=2;i<=20;i++)
    {
        lcm=FindLcm(lcm,i);
    }
    System.out.println("Lcm="+lcm);
}

它实现了一个相当不错的算法。您的问题是您FindLcm()包含一个令人讨厌的性能错误。

static long FindLcm(long a,long b)
{
    long lcm,hcf = 0;
    long i=1;
    // This sets ger to max(a,b) - why?
    long ger=a>b?a:b;
    // This would return a wrong result if a == b
    // that never happens here, though
    while(i<ger)
    {
        if((a%i==0) && (b%i==0))
            hcf=i;
        i++;
    }
    lcm=(a*b)/hcf;
    return lcm;
}

您正在循环，直到达到两个参数中较大的一个。由于累积的 LCM 增长相当快，这需要很多时间。但是两个（正）数的 GCD（或 HCF，如果您愿意的话）不能大于两者中较小的一个。因此，仅循环直到达到两个参数中的较小者，使得这里的迭代次数最多为 20，执行 19 次（for i = 2, ..., 20），这是一个微不足道的计算量。

更改为

long ger = a < b ? a : b;
while(i <= ger) {

给我（添加计时码，不测量打印）：

17705 nanoseconds
Lcm=232792560

因此计算时间不到 20微秒。如果我们使用欧几里得算法找到最大公约数，我们可以轻松地将其推到 6 微秒以下，

static long gcd(long a, long b) {
    while(b > 0) {
        a %= b;
        if (a == 0) return b;
        b %= a;
    }
    return a;
}

如果我们直接使用 GCD 作为，则低于 5

lcm *= i/gcd(lcm,i);

在FindMultiple().

于 2012-12-07T15:23:28.660 回答
4

你的解决方案或多或少是蛮力，这就是为什么它需要这么长时间。我们知道 2520 是 (1,2,...,9,10) 的 lcm，这意味着两个有用的东西：1.）我们可以从 11 和 2 开始检查因数。）答案是 2520 的倍数。

您正在搜索答案的最大公约数 (gcd) 和序列中的下一个数字（类似于冒泡排序）。您可以检查您当前的答案是否可以被下一个因子整除，如果不是，则将您当前的答案添加到自身，直到答案可以被下一个因子整除。例如：

    static long findLCM(long a, long b) {
        long lcm = (a>b) ? a : b;
        while (lcm % b != 0) {
            lcm += a;
        }
        return lcm;
    }

由于我们从 lcm = a 开始，我们知道只要我们将 a 加到 lcm 上，那么 lcm 就总是能被 a 整除。现在，我们只需要使 a 可以被 b 整除。这个过程应该省去许多首先找到 gcd 以及从 2 到 10 迭代的步骤。

于 2012-12-06T04:55:44.240 回答
2

我是这样做的，这是我能想到的最简单的方法。它也比你的快一点。

    for(int i = 190; ; i += 190) {
        if(i % 3 == 0 
                && i % 4 == 0
                && i % 6 == 0 
                && i % 7 == 0
                && i % 8 == 0 
                && i % 9 == 0
                && 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 % 20 == 0) {
            System.out.println(i);
            break;
        }
    }
于 2012-12-05T10:13:32.783 回答
2

这里有4种不同的方法来获得结果（4种不同的方法来获得GCD）+总时间。所有这些都基于以下观察：

              a*b
lcm(a,b) = ---------- 
            gcd(a,b)

在哪里：

LCM = 最小公倍数
GCD = 最大公约数

import java.lang.reflect.Method;
import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;

public class A {

    final static int N = 20;

    static Map<Integer, String> messages = new HashMap<>();

    static {
        messages.put(0, "Euler - difference");
        messages.put(1, "modulo - recursive");
        messages.put(2, "modulo - iterative");
        messages.put(3, "BigInteger implementation");
    }

    private static long GCD0(long x, long y) {
        while (x != y) {
            if (x > y) {
                x -= y;
            } else {
                y -= x;
            }
        }
        return x;
    }

    private static long GCD1(long x, long y) {
        if (x % y == 0) {
            return y;
        }
        return GCD1(y, x % y);
    }

    private static long GCD2(long x, long y) {
        long aux;
        while (x % y != 0) {
            aux = y;
            y = x % y;
            x = aux;
        }
        return y;
    }

    private static long GCD3(long x, long y) {
        BigInteger xx = BigInteger.valueOf(x);
        BigInteger yy = BigInteger.valueOf(y);
        return xx.gcd(yy).longValue();
    }

    private static void doIt(int pos) throws Exception {

        System.out.print("\n" + messages.get(pos));
        printSpaces(25, messages.get(pos).length());

        Class cls = Class.forName("A");
        Object obj = cls.newInstance();
        Method method = cls.getDeclaredMethod("GCD" + pos, long.class,
                long.class);

        long start = System.nanoTime();

        long p = 1;
        for (int i = 2; i <= N; i++) {
            p = (p * i) / (long) method.invoke(obj, p, i);
        }
        long stop = System.nanoTime();
        System.out.println("\tTime: " + (stop - start) / 1000 + " microseconds");
        System.out.println(p);
    }

    private static void printSpaces(int total, int actualLength) {
        for (int i = 0; i < total - actualLength; i++) {
            System.out.print(" ");
        }
    }

    public static void main(String[] args) throws Exception {
        doIt(0);
        doIt(1);
        doIt(2);
        doIt(3);
    }
}

输出：

Euler - difference          Time: 137205 microseconds
232792560

modulo - recursive          Time: 1240 microseconds
232792560

modulo - iterative          Time: 1228 microseconds
232792560

BigInteger implementation   Time: 2984 microseconds
232792560

PS：我使用反射来调用这些方法更容易，但是您可以直接调用该方法以获得更好的性能+更好的可读性。

于 2014-11-10T22:08:25.740 回答
1 
int i = 20;
        while (true)
        {
        if (    
                    (i % 1 == 0) &&
                    (i % 2 == 0) &&
                    (i % 3 == 0) &&
                    (i % 5 == 0) &&
                    (i % 7 == 0) &&
                    (i % 9 == 0) &&
                    (i % 11 == 0) &&
                    (i % 13 == 0) &&
                    (i % 16 == 0) &&
                    (i % 17 == 0) &&
                    (i % 19 == 0) )
            {
                break;
            }
            i += 20;
        }
S.O.P(i);
于 2013-08-23T05:41:45.603 回答
1

具有最少迭代的 C++ 程序...非常类似于 Daniel Fischer

#include<iostream>

using namespace std;

int main()
{
    int num = 20;
    long lcm = 1L;
    for (int i = 2; i <= num; i++)
    {
        int hcf = 1;
        for (int j = 2; j <= i; j++)
        {
            if (i % j == 0 && lcm % j == 0)
            {
                hcf = j;
            }
        }
        lcm = (lcm * i) / hcf;
    }
    cout << lcm << "\n";
}
于 2014-04-01T16:16:09.500 回答
1

此方法使用蛮力，但一旦数字失败就跳过而不是继续比较余数。哎呀，除非已经通过了 19，否则它永远不会检查 20，这实际上使它非常有效。

#include<stdio.h>
int a = 1, b = 1, rem;
int main() {
    while (b < 20){
        rem = a % b;
        if (rem != 0){
            a++;
            b = 1;
        }
        b++;
        }
    printf("%d is the smallest positive number divisible by all of the numbers from 1 to 20.", a);
}
于 2017-06-19T06:07:36.223 回答
0

一种非蛮力方法

这个是瞬间的！甚至不需要一秒钟。运行代码以了解逻辑。它是用 C 写的

#include <stdio.h>

int main()  {

int primes[8]={2,3,5,7,11,13,17,19};
int primes_count[8]={0,0,0,0,0,0,0,0};
int i,j,num,prime_point;
int largest_num=1;

printf("\nNUM");
for(j=0;j<8;j++)
    printf("\t%d",primes[j]);

for(i=2;i<=20;i++)  {
    num=i;
    int primes_count_temp[8]={0,0,0,0,0,0,0,0};
    for(j=0;j<8;j++)    {
        while(num%primes[j]==0) {
            num=num/primes[j];
            primes_count_temp[j]++;
        }
    }
    for(j=0;j<8;j++)
        if(primes_count_temp[j]>primes_count[j])
            primes_count[j]=primes_count_temp[j];

        printf("\n %d",i);
        for(j=0;j<8;j++)
            printf("\t %d",primes_count_temp[j]);
    }
    printf("\nNET");
    for(j=0;j<8;j++)
        printf("\t%d",primes_count[j]);
    printf("\n");
    for(i=0;i<8;i++)
        while(primes_count[i])  {
            largest_num*=primes[i];
            primes_count[i]--;
        }

        printf("The answer is %d \n",largest_num);
        return 0;
    }

现在，如果一个数能被 X 整除，那么它也能被它的素因数整除。因此，如果一个数能被 20 整除，那么它就能被它的质因数整除。并且有 8 个 20 以下的素数。我取每个 20 以下的数并找到它的素因数，同时查看素数的幂并计算最高幂。

一旦你完成了。将所有素因数乘以最高幂。

于 2014-05-01T13:11:03.157 回答
0

我在 python 中的解决方案。这很简单，使用纯数学规则

得到最小公倍数

def getLCM (x, y):
  return x*y/getGCD(x,y)

得到最大公约数

def getGCD(a,b):
   while(True):
      if(a%b != 0):
          temp = b
          b = a%b
          a = temp
      else:
          return b
          break

查找列表中前两个数字和下一个数字的 LCM 的最小公倍数。

LCM（前两个数字的LCM，列表中的下一个数字）

num_list = list(range(1,21))
finalLCM = 1
for i in num_list:
  finalLCM = getLCM(finalLCM,i)
print(finalLCM)

完整的 Python 代码

def getLCM (x, y):
return x*y/getGCD(x,y)

def getGCD(a,b):
  while(True):
      if(a%b != 0):
         temp = b
         b = a%b
         a = temp
      else:
         return b
         break

num_list = list(range(1,21))
finalLCM = 1

for i in num_list:
  finalLCM = getLCM(finalLCM,i)
print(finalLCM)
于 2016-10-16T15:59:35.400 回答
0

我们已经创建了一个可以被 20 整除的数组，例如：如果任何数字都可以被 20 整除，那么就不需要被 2,4,5,10 整除

<?php
$chk=20;

$div=array(11,12,13,14,15,16,17,18,19,20);
for($number=1;1;$number++){
    $chk=$number;
    foreach($div as $value){        
        if($number%$value!=0){
            $chk=0;
            $number+=$value;
            break;
        }
    }
    if($chk!=0){break;}
}
echo $chk;
?>
于 2018-05-02T10:32:23.403 回答