java Project Euler #5（可被 1 到 20 的所有数字整除的最小正数）：优化方法？~爪哇
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/13719768/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Project Euler #5(Smallest positive number divisible by all numbers from 1 to 20): Ways to Optimize? ~Java
提问by Akhil Jain
Problem 5:2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
问题 5：2520 是 1 到 10 中的每一个数都可以整除而没有余数的最小数。能被 1 到 20 的所有数整除的最小正数是多少？
I have solved the problem 5 of Project Euler
我已经解决了Project Euler的问题5
Here is the Java code:
这是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);
}
How can optimize this?
如何优化这个？
回答by Daniel Fischer
Your FindMultiple()method is not bad,
你的FindMultiple()方法不错，
static void FindMultiple()
{
long lcm=1;
for(long i=2;i<=20;i++)
{
lcm=FindLcm(lcm,i);
}
System.out.println("Lcm="+lcm);
}
it implements a fairly good algorithm. Your problem is that your FindLcm()contains a nasty performance bug.
它实现了一个相当好的算法。您的问题是您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;
}
You are looping until you reach the largerof the two arguments. Since the cumulative LCMs grow rather fast, that takes a lot of time. But the GCD (or HCF, if you prefer) of two (positive) numbers cannot be larger than the smaller of the two. So looping only until the smaller of the two arguments is reached makes the number of iterations at most 20 here, do that 19 times (for i = 2, ..., 20), it's a trivial amount of computation.
您一直在循环，直到达到两个参数中较大的一个。由于累积 LCM 增长得相当快，这需要很多时间。但是两个（正）数的 GCD（或 HCF，如果您愿意）不能大于两者中较小的一个。因此，仅循环直到达到两个参数中较小的一个，此处的迭代次数最多为 20，执行 19 次（对于i = 2, ..., 20），这是一个微不足道的计算量。
Changing to
更改为
long ger = a < b ? a : b;
while(i <= ger) {
gives me (adding timing code, not measuring the printing):
给我（添加计时代码，而不是测量打印）：
17705 nanoseconds
Lcm=232792560
So less than 20 microsecondsfor the computation. We can easily push that below 6 microseconds if we use the euclidean algorithm to find the greatest common divisor,
所以计算时间不到 20微秒。如果我们使用欧几里得算法找到最大公约数，我们可以轻松地将其推到 6 微秒以下，
static long gcd(long a, long b) {
while(b > 0) {
a %= b;
if (a == 0) return b;
b %= a;
}
return a;
}
and below 5 if we directly use the GCD as
如果我们直接使用 GCD 作为，则低于 5
lcm *= i/gcd(lcm,i);
in FindMultiple().
在FindMultiple().
回答by Fennelouski
You're solution is more or less brute force which is why it's taking so long. We know that 2520 is the lcm of (1,2,...,9,10) which means two useful things: 1.) We can start checking factors at 11 and 2.) The answer is a multiple of 2520.
你的解决方案或多或少是蛮力，这就是为什么它需要这么长时间。我们知道 2520 是 (1,2,...,9,10) 的 lcm，这意味着两件事：1.) 我们可以开始检查 11 和 2 处的因子。) 答案是 2520 的倍数。
You're searching for the Greatest Common Divisor (gcd) of the answer and the next number in your sequence (similar to a bubble sort). You could just check to see if your current answer is divisible by the next factor and if not then add your current answer to itself until the answer is divisible by the next factor. For Example:
您正在搜索答案的最大公约数 (gcd) 和序列中的下一个数字（类似于冒泡排序）。您可以检查一下您当前的答案是否可以被下一个因素整除，如果不是，则将您当前的答案添加到自身，直到答案可以被下一个因素整除。例如：
static long findLCM(long a, long b) {
long lcm = (a>b) ? a : b;
while (lcm % b != 0) {
lcm += a;
}
return lcm;
}
Since we started with lcm = a, we know that as long as we add a's to lcm then lcm will always be divisible by a. Now, we just need to make some multiple of a divisible by b. This process should cut out many steps of first finding the gcd as well as iterating from 2 through 10.
由于我们从 lcm = a 开始，我们知道只要我们在 lcm 上加上 a，那么 lcm 就可以被 a 整除。现在，我们只需要使 a 的一些倍数可以被 b 整除。这个过程应该省去很多步骤，比如首先找到 gcd 以及从 2 到 10 的迭代。
回答by dicheridoo
i did it like this, which was the easiest way i could think of. it's also a little faster than yours.
我是这样做的，这是我能想到的最简单的方法。它也比你的快一点。
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;
}
}
回答by ROMANIA_engineer
Here are 4 different methodsto obtain the result (4 different ways to obtain GCD) + the total time. All of them are based on the following observation:
这里有4 种不同的方法来获得结果（4 种不同的方式获得 GCD）+总时间。所有这些都基于以下观察：
a*b lcm(a,b) = ---------- gcd(a,b)
a*b lcm(a,b) = ---------- gcd(a,b)
where:
在哪里：
LCM = Least Common Multiple
GCD = Greatest Common Divisor
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);
}
}
Output:
输出：
Euler - difference Time: 137205 microseconds
232792560
modulo - recursive Time: 1240 microseconds
232792560
modulo - iterative Time: 1228 microseconds
232792560
BigInteger implementation Time: 2984 microseconds
232792560
P.S.: I used reflectionto call those methods easier, but you can call the method directly to obtain a better performance + a better readability.
PS：我使用反射来调用这些方法更容易，但是您可以直接调用该方法以获得更好的性能+更好的可读性。
回答by Android learner
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);
回答by Love Sharma
C++ Program with minimum iteration... very much resemble to Daniel Fischer
最小迭代的 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";
}
回答by Scientia Vult
This method uses brute force, but skips as soon as a number fails instead of continuing to compare the remainders. Heck, it never checks for 20 unless 19 has passed already, which actually makes it pretty efficient.
此方法使用蛮力，但在数字失败时立即跳过，而不是继续比较余数。哎呀，除非 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);
}
回答by Abhijeet Navgire
we have create an array which was common divisible eg: if any number is divisible by 20 then no need to divisible by 2,4,5,10
我们创建了一个可以被整除的数组，例如：如果任何数字可以被 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;
?>
回答by chetan92
A Non Brute Force Method
一种非蛮力方法
This one is instantaneous! Doesn't even take a second. Run the code to understand the logic. It's written in C
这个是瞬间的！甚至不需要一秒钟。运行代码以了解逻辑。它是用 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;
}
Now if a number is divisible by X it will be divisible by its prime factors also. So if a number is divisible by 20 it will be divisible by its prime factors. And there are 8 prime factors under 20. I take each number under 20 and find its prime factors, also see the power of the prime factor and keep a count of the highest power.
现在，如果一个数能被 X 整除，那么它也能被它的质因数整除。因此，如果一个数能被 20 整除，它就能被它的质因数整除。20以下有8个质因数。我取20以下的每个数，找出它的质因数，也看质因数的幂，并计算出最高的幂。
Once you're done. Multiply all the prime factors raised to their highest power.
一旦你完成。将所有素因数乘以最高幂。
回答by Tatzone
my Solution for this in python. this is so simple and use pure Math rules
我在 python 中的解决方案。这很简单，使用纯数学规则
get the Least Common Multiple
得到最小公倍数
def getLCM (x, y):
return x*y/getGCD(x,y)
get the Greatest Common Divisor
得到最大公约数
def getGCD(a,b):
while(True):
if(a%b != 0):
temp = b
b = a%b
a = temp
else:
return b
break
Find the Least Common Multiple of, LCM of prev two numbers and next number in list.
找到列表中前两个数字和下一个数字的 LCM 的最小公倍数。
LCM(LCM of prev two numbers,next number in list)
LCM（前两个数字的LCM，列表中的下一个数字）
num_list = list(range(1,21))
finalLCM = 1
for i in num_list:
finalLCM = getLCM(finalLCM,i)
print(finalLCM)
Full Python Code
完整的 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)
