There is another recent Project Euler question but I think this is a bit more specific (I'm only really interested in PHP based solutions) so I'm asking anyway.
还有另一个最近的Project Euler问题,但我认为这有点具体(我只对基于PHP的解决方案感兴趣)所以我还是要问。
Question #5 tasks you with: "What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?"
问题#5的任务是:“从1到20的所有数字均可被整除的最小数字是多少?”
Now, I have solved it twice. Once very inefficiently and once much more efficiently but I am still far away from an especially sophisticated answer (and I am not especially solid in math hence my brute force solution). I can see a couple of areas where I could improve this but I am wondering if any of you could demonstrate a more efficient solution to this problem.
现在,我已经解决了两次。曾经非常低效,而且效率更高,但我仍然远离一个特别复杂的答案(我在数学上并不是特别坚固,因此我的蛮力解决方案)。我可以看到几个方面我可以改进这个,但我想知道你们中是否有人能够证明这个问题更有效的解决方案。
*spoiler: Here is my less than optimal (7 seconds to run) but still tolerable solution (not sure what to do about the double $... just pretend you only see 1...
*扰流板:这是我不太理想(7秒运行)但仍然可以容忍的解决方案(不知道如何处理双$ ...只是假装你只看到1 ......
function euler5(){
$x = 20;
for ($y = 1; $y < 20; $y++) {
if (!($x%$y)) {
} else {
$x+=20;
$y = 1;
}
}echo $x;
};
8 个解决方案
#1
3
in php it will look like this:
在PHP中它将如下所示:
<?php
function gcd($a,$b) {
while($a>0 && $b>0) {
if($a>$b) $a=$a-$b; else $b=$b-$a;
}
if($a==0) return $b;
return $a;
}
function euler5($i=20) {
$euler=$x=1;
while($x++<$i) {
$euler*=$x/gcd($euler,$x);
}
return $euler;
}
?>
Its at least twice as fast than what you posted.
它至少比你发布的快两倍。
#2
6
Collect prime factors for all numbers between 1 and 20. Counting the maximal exponents of each prime factor, we have 16 = 2**4, 9 = 3**2, as well as 5, 7, 11, 13, 17, 19 (each appearing only once). Multiply the lot, and you have your answer.
收集1到20之间所有数字的素因子。计算每个素数因子的最大指数,我们得到16 = 2 ** 4,9 = 3 ** 2,以及5,7,11,13,17,19 (每个只出现一次)。乘以这个地段,你就得到了答案。
#3
2
Chris Jester-Young is right.
Chris Jester-Young是对的。
In general if you wanted the smallest number that is evenly divisible by all of the numbers from 1 to N, you would want to find all the prime numbers from 2 to N, and for each one, find the greatest number of times it divides any number in the range. This can be calculated by finding the greatest power of the prime that's not greater than N.
一般来说,如果你想要从1到N的所有数字都可以整除的最小数字,你可能希望找到从2到N的所有素数,并且对于每一个,找到它划分的最大次数。范围内的数字。这可以通过找到不大于N的素数的最大幂来计算。
In the case of 20, as Chris pointed out, 2^4 is the greatest power of 2 not greater than 20, and 3^2 is the greatest power of 3 not greater than 20, and for all other primes, only the first power is not greater than 20.
在20的情况下,克里斯指出,2 ^ 4是2的最大功率不大于20,3 ^ 2是3的最大功率不大于20,而对于所有其他素数,只有第一次幂不超过20。
#4
2
You can remove some numbers that are divided with, for example 1 is unnecessary, all natural numbers are divisible by 1.you don’t need 2 either, and therefore, all numbers are divisible by multiples of 2 (4, 8, 16, etc) are divisible by 2, also. So the relevant numbers will be 11, 12, 13, 14, 15, 16, 17, 18, and 19.
你可以删除一些被划分的数字,例如1是不必要的,所有自然数都可以被1整除。你也不需要2,因此,所有数字都可以被2的倍数整除(4,8,16,等)也可被2整除。因此相关的数字将是11,12,13,14,15,16,17,18和19。
So:
<?
function eulerPuzzle()
{
$integers = array( 11,12,13,14,15,16,17,18,19 );
for ($n = 20; 1; $n += 20 ) {
foreach ($integers as $int) {
if ( $n % $int ) {
break;
}
if ( $int == 19 ) {
die ("Result:" . $n);
}
}
}
}
eulerPuzzle();
?>
#5
1
<?php
$i=20;
while ($i+=20) {
for ($j=19;$j!==10;--$j){
if ($i%$j) continue 2;
}
die ("result: $i\n");
}
Is the fastest and shortest php solution so far. About 1.4x faster than Czimi's on my comp. But check out the python solution, thats a nice algo.
到目前为止,是最快和最短的PHP解决方案。比我的comp上的Czimi快约1.4倍。但是查看python解决方案,这是一个不错的算法。
#6
0
Some people really over-think this...
有些人真的过度思考这个......
In Ruby:
puts 5*7*9*11*13*16*17*19
#7
0
@People doing simple math; I'm not sure if that is the goal of the exercise. You are to learn new languages and new ways to perform stuff. Just doing it by a calculator isn't the right way going about things.
@People做简单的数学;我不确定这是否是演习的目标。你将学习新的语言和新的方法来执行东西。用计算器做这件事并不是正确的事情。
And I know this is a post in an old old thread but it still comes up in google results :)
我知道这是旧帖子中的帖子,但它仍然出现在谷歌搜索结果:)
Doing it in code (PHP that is) I found this to be the fastest solution:
在代码中执行此操作(即PHP)我发现这是最快的解决方案:
function eulerPuzzle() {
$integers = array (11, 12, 13, 14, 15, 16, 17, 18, 19 );
for($n = 2520; 1; $n += 2520) {
foreach ( $integers as $int ) {
if ($n % $int) {
break;
}
if ($int == 19) {
die ( "Result:" . $n );
}
}
}
}
eulerPuzzle ();
Yes, it's a modified piece from CMS. The main reason it is faster is because when you read the question, they already state that the lowest possible number for the first 10 integers is 2520. therefor, you can just increment by 2520 instead of 20. resulting in 126 times less loops
是的,这是来自CMS的改进版。它更快的主要原因是因为当你读到这个问题时,他们已经说出前10个整数的最低可能数是2520.因此,你可以增加2520而不是20,导致循环减少126倍
#8
-1
I know you said PHP, but here's my rough draft in Python.
我知道你说的是PHP,但这是我在Python中的草稿。
#!/usr/bin/env python
from operator import mul
def factor(n):
factors = {}
i = 2
while i < n and n != 1:
while n % i == 0:
try:
factors[i] += 1
except KeyError:
factors[i] = 1
n = n / i
i += 1
if n != 1:
factors[n] = 1
return factors
base = {}
for i in range(2, 2000):
for f, n in factor(i).items():
try:
base[f] = max(base[f], n)
except KeyError:
base[f] = n
print reduce(mul, [f**n for f, n in base.items()], 1)
It's not as elegant as I could have made it, but it calculates the least common multiple of the numbers from 2 to 2000 in .15s. If your iterative solution could process a billion candidates per second, it would take 10^849 years to finish.
它并不像我能做到的那么优雅,但它计算出的最小公倍数从2到2000,在15秒内。如果您的迭代解决方案每秒可以处理十亿个候选人,则需要10 ^ 849年才能完成。
In other words, don't bother optimizing the wrong algorithm.
换句话说,不要打扰优化错误的算法。
#1
3
in php it will look like this:
在PHP中它将如下所示:
<?php
function gcd($a,$b) {
while($a>0 && $b>0) {
if($a>$b) $a=$a-$b; else $b=$b-$a;
}
if($a==0) return $b;
return $a;
}
function euler5($i=20) {
$euler=$x=1;
while($x++<$i) {
$euler*=$x/gcd($euler,$x);
}
return $euler;
}
?>
Its at least twice as fast than what you posted.
它至少比你发布的快两倍。
#2
6
Collect prime factors for all numbers between 1 and 20. Counting the maximal exponents of each prime factor, we have 16 = 2**4, 9 = 3**2, as well as 5, 7, 11, 13, 17, 19 (each appearing only once). Multiply the lot, and you have your answer.
收集1到20之间所有数字的素因子。计算每个素数因子的最大指数,我们得到16 = 2 ** 4,9 = 3 ** 2,以及5,7,11,13,17,19 (每个只出现一次)。乘以这个地段,你就得到了答案。
#3
2
Chris Jester-Young is right.
Chris Jester-Young是对的。
In general if you wanted the smallest number that is evenly divisible by all of the numbers from 1 to N, you would want to find all the prime numbers from 2 to N, and for each one, find the greatest number of times it divides any number in the range. This can be calculated by finding the greatest power of the prime that's not greater than N.
一般来说,如果你想要从1到N的所有数字都可以整除的最小数字,你可能希望找到从2到N的所有素数,并且对于每一个,找到它划分的最大次数。范围内的数字。这可以通过找到不大于N的素数的最大幂来计算。
In the case of 20, as Chris pointed out, 2^4 is the greatest power of 2 not greater than 20, and 3^2 is the greatest power of 3 not greater than 20, and for all other primes, only the first power is not greater than 20.
在20的情况下,克里斯指出,2 ^ 4是2的最大功率不大于20,3 ^ 2是3的最大功率不大于20,而对于所有其他素数,只有第一次幂不超过20。
#4
2
You can remove some numbers that are divided with, for example 1 is unnecessary, all natural numbers are divisible by 1.you don’t need 2 either, and therefore, all numbers are divisible by multiples of 2 (4, 8, 16, etc) are divisible by 2, also. So the relevant numbers will be 11, 12, 13, 14, 15, 16, 17, 18, and 19.
你可以删除一些被划分的数字,例如1是不必要的,所有自然数都可以被1整除。你也不需要2,因此,所有数字都可以被2的倍数整除(4,8,16,等)也可被2整除。因此相关的数字将是11,12,13,14,15,16,17,18和19。
So:
<?
function eulerPuzzle()
{
$integers = array( 11,12,13,14,15,16,17,18,19 );
for ($n = 20; 1; $n += 20 ) {
foreach ($integers as $int) {
if ( $n % $int ) {
break;
}
if ( $int == 19 ) {
die ("Result:" . $n);
}
}
}
}
eulerPuzzle();
?>
#5
1
<?php
$i=20;
while ($i+=20) {
for ($j=19;$j!==10;--$j){
if ($i%$j) continue 2;
}
die ("result: $i\n");
}
Is the fastest and shortest php solution so far. About 1.4x faster than Czimi's on my comp. But check out the python solution, thats a nice algo.
到目前为止,是最快和最短的PHP解决方案。比我的comp上的Czimi快约1.4倍。但是查看python解决方案,这是一个不错的算法。
#6
0
Some people really over-think this...
有些人真的过度思考这个......
In Ruby:
puts 5*7*9*11*13*16*17*19
#7
0
@People doing simple math; I'm not sure if that is the goal of the exercise. You are to learn new languages and new ways to perform stuff. Just doing it by a calculator isn't the right way going about things.
@People做简单的数学;我不确定这是否是演习的目标。你将学习新的语言和新的方法来执行东西。用计算器做这件事并不是正确的事情。
And I know this is a post in an old old thread but it still comes up in google results :)
我知道这是旧帖子中的帖子,但它仍然出现在谷歌搜索结果:)
Doing it in code (PHP that is) I found this to be the fastest solution:
在代码中执行此操作(即PHP)我发现这是最快的解决方案:
function eulerPuzzle() {
$integers = array (11, 12, 13, 14, 15, 16, 17, 18, 19 );
for($n = 2520; 1; $n += 2520) {
foreach ( $integers as $int ) {
if ($n % $int) {
break;
}
if ($int == 19) {
die ( "Result:" . $n );
}
}
}
}
eulerPuzzle ();
Yes, it's a modified piece from CMS. The main reason it is faster is because when you read the question, they already state that the lowest possible number for the first 10 integers is 2520. therefor, you can just increment by 2520 instead of 20. resulting in 126 times less loops
是的,这是来自CMS的改进版。它更快的主要原因是因为当你读到这个问题时,他们已经说出前10个整数的最低可能数是2520.因此,你可以增加2520而不是20,导致循环减少126倍
#8
-1
I know you said PHP, but here's my rough draft in Python.
我知道你说的是PHP,但这是我在Python中的草稿。
#!/usr/bin/env python
from operator import mul
def factor(n):
factors = {}
i = 2
while i < n and n != 1:
while n % i == 0:
try:
factors[i] += 1
except KeyError:
factors[i] = 1
n = n / i
i += 1
if n != 1:
factors[n] = 1
return factors
base = {}
for i in range(2, 2000):
for f, n in factor(i).items():
try:
base[f] = max(base[f], n)
except KeyError:
base[f] = n
print reduce(mul, [f**n for f, n in base.items()], 1)
It's not as elegant as I could have made it, but it calculates the least common multiple of the numbers from 2 to 2000 in .15s. If your iterative solution could process a billion candidates per second, it would take 10^849 years to finish.
它并不像我能做到的那么优雅,但它计算出的最小公倍数从2到2000,在15秒内。如果您的迭代解决方案每秒可以处理十亿个候选人,则需要10 ^ 849年才能完成。
In other words, don't bother optimizing the wrong algorithm.
换句话说,不要打扰优化错误的算法。