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;
}

2 つの引数のうち大きい方に到達するまでループします。累積的な LCM は急速に成長するため、かなりの時間がかかります。ただし、2 つの (正の) 数値の GCD (または必要に応じて HCF) は、2 つの小さい方よりも大きくすることはできません。したがって、2 つの引数のうち小さい方に到達するまでループすると、反復回数は最大で 20 回になり、( の場合i = 2, ..., 20) 19 回実行されます。計算量はわずかです。

に変更

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 であることはわかっていますが、これは 2 つの有用なことを意味します: 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 で割り切れることがわかります。ここで、b で割り切れる a の倍数を作成する必要があります。このプロセスにより、最初に 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 つの異なる方法(GCD を取得するための 4 つの異なる方法) +合計時間を次に示します。それらはすべて、次の観察に基づいています。

              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

反復が最小限の 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 
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 に答える
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

リスト内の前の 2 つの数字と次の数字の最小公倍数、最小公倍数を見つけます。

LCM(前の 2 つの数字の 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 で割り切れる数がある場合、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 に答える