Um projecto de Euler Puzzler (especificamente em PHP)

Question

Há uma outra questão recente Projeto Euler, mas eu acho que isso é um pouco mais específico (eu só estou realmente interessado em soluções baseadas em PHP) por isso estou pedindo qualquer maneira.

Pergunta # 5 tarefas você: "Qual é o menor número que é divisível por todos os números de 1 a 20? "

Agora, eu ter resolvido-lo duas vezes. Uma vez que muito ineficiente e uma vez com muito mais eficiência, mas ainda estou muito longe de uma resposta especialmente sofisticada (e eu não sou especialmente sólida em matemática daí a minha solução de força bruta). Eu posso ver um par de áreas onde eu poderia melhorar isso, mas eu estou querendo saber se algum de vocês poderia demonstrar uma solução mais eficiente para este problema.

* Spoiler: Aqui está o meu abaixo do ideal (7 segundos para correr), mas ainda tolerável solução (não sei o que fazer sobre o duplo $ ... apenas fingir que você só vê uma ...

    function euler5(){
        $x = 20;

        for ($y = 1; $y < 20; $y++) {

            if (!($x%$y)) {

            } else {  
                $x+=20;
                $y = 1;  
            }   

        }echo $x;
     };

Answer 1

em php que será parecido com este:

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

?>

Sua pelo menos duas vezes mais rápido do que o que você postou.

Answer 2

factores primos Collect para todos os números entre 1 e 20. Contando os expoentes máximas de cada um destes factores se, temos 16 = 2**4, 9 = 3**2, bem como 5, 7, 11, 13, 17, 19 (cada aparecendo apenas uma vez). Multiplique o lote, e você tem sua resposta.

Answer 3

Chris Jester-Young é certo.

Em geral, se você queria o menor número que é divisível por todos os números de 1 a N, que você gostaria de encontrar todos os números primos de 2 a N, e para cada um, encontrar o maior número de vezes divide-se qualquer número no intervalo. Isto pode ser calculado por encontrar o maior poder do nobre que não é maior do que N.

No caso de 20, como Chris apontou, 2 ^ 4 é a maior potência de 2 não superior a 20, e 3 ^ 2 é o maior poder de 3 não superior a 20, e para todos os outros primos, única a primeira potência não superior a 20.

Answer 4

Você pode remover alguns números que são divididos com, por exemplo 1 é desnecessária, todos os números naturais são divisíveis por 1.you não precisa de 2 quer, e, portanto, todos os números são divisíveis por múltiplos de 2 (4, 8 , 16, etc.) são divisível por 2, também. Assim, os números relevantes será de 11, 12, 13, 14, 15, 16, 17, 18, e 19.

Assim:

<?
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();
?>

Answer 5

<?php
$i=20;
while ($i+=20) {
    for ($j=19;$j!==10;--$j){
        if ($i%$j) continue 2;
    }
    die ("result: $i\n");
}

É a solução mais rápida e mais curta php até agora. Sobre 1,4x mais rápido do que Czimi de no meu comp. Mas confira a solução python, isso é um algo agradável.

Answer 6

Algumas pessoas realmente excesso de pensar isso ...

Em Ruby:

puts 5*7*9*11*13*16*17*19

Answer 7

@People fazendo matemática simples; Eu não tenho certeza se esse é o objetivo do exercício. Você está a aprender novas linguagens e novas maneiras de realizar coisas. Apenas fazê-lo por uma calculadora não é o caminho certo fazer as coisas.

E eu sei que este é um post em uma velha discussão antiga, mas ainda aparece nos resultados do Google:)

Fazê-lo em código (PHP que é) Eu encontrei este para ser a solução mais rápida:

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 ();

Sim, é uma peça modificada a partir de CMS. A principal razão é mais rápido porque, quando você ler a pergunta, eles já afirmam que o menor número possível para os primeiros 10 inteiros é 2520. mesmos, você pode simplesmente incrementado em 2520 em vez de 20. resultando em 126 vezes menos laços

Answer 8

Eu sei que você disse PHP, mas aqui está o meu rascunho em 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)

Não é tão elegante como eu poderia ter feito isso, mas ele calcula o mínimo múltiplo comum dos números 2-2000 em .15s. Se a sua solução iterativa poderia processar um bilhão de candidatos por segundo, levaria 10 ^ 849 anos para terminar.

Em outras palavras, não se incomode otimizar o algoritmo errado.