Un projet Euler Puzzler (en particulier en PHP)

Question

Il y a une autre question récente sur le projet Euler, mais je pense que c'est un peu plus spécifique (les solutions basées sur PHP ne m'intéressent que beaucoup), alors je pose quand même la question.

La

la question n ° 5 vous charge: & Quelle est la plus petite nombre qui est divisible par tous les nombres de 1 à 20? "

Maintenant, je l'ai résolu deux fois. Une fois très inefficace et une fois beaucoup plus efficacement, mais je suis encore loin d'une réponse particulièrement sophistiquée (et je ne suis pas particulièrement solide en math, d'où ma solution de force brute). Je vois quelques domaines dans lesquels je pourrais améliorer cela, mais je me demande si l’un d’entre vous pourrait démontrer une solution plus efficace à ce problème.

* spoiler: Voici ma solution moins qu'optimale (7 secondes pour fonctionner) mais toujours tolérable (vous ne savez pas quoi faire avec le double $ ... prétendez que vous n'en voyez que 1 ...

    function euler5(){
        $x = 20;

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

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

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

        }echo $x;
     };

Answer 1

en php cela ressemblera à ceci:

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

?>

C'est au moins deux fois plus vite que ce que vous avez posté.

Answer 2

Recueillez les facteurs premiers pour tous les nombres compris entre 1 et 20. En comptant les exposants maximaux de chaque facteur premier, nous avons 16 = 2 ** 4 , 9 = 3 ** 2 , ainsi que 5, 7, 11, 13, 17, 19 (chacun apparaissant une seule fois). Multipliez le lot et vous avez votre réponse.

Answer 3

Chris Jester-Young a raison.

En général, si vous vouliez le plus petit nombre qui soit divisible par tous les nombres de 1 à N, vous voudriez trouver tous les nombres premiers de 2 à N, et pour chacun trouver le plus grand nombre de fois. il divise n'importe quel nombre dans la plage. Ceci peut être calculé en trouvant la plus grande puissance du nombre premier qui ne soit pas supérieure à N.

Dans le cas de 20, comme Chris l'a souligné, 2 ^ 4 est la plus grande puissance de 2 non supérieure à 20 et 3 ^ 2 est la plus grande puissance de 3 non supérieure à 20, et pour tous les autres nombres premiers, uniquement le premier pouvoir n'est pas supérieur à 20.

Answer 4

Vous pouvez supprimer certains nombres divisés avec, par exemple, 1 est inutile, tous les nombres naturels sont divisibles par 1.vous n'avez pas besoin de 2 non plus, et par conséquent, tous les nombres sont divisibles par multiples de 2 (4, 8 , 16, etc.) sont divisibles par 2, également. Les numéros pertinents seront donc les 11, 12, 13, 14, 15, 16, 17, 18 et 19.

Donc:

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

Est la solution php la plus rapide et la plus courte à ce jour. Environ 1,4 fois plus rapide que Czimi sur mon ordinateur. Mais jetez un œil à la solution python, c’est un bon algo.

Answer 6

Certaines personnes pensent trop à cela ...

En Ruby:

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

Answer 7

@Personnes faisant des calculs simples; Je ne suis pas sûr que ce soit le but de l'exercice. Vous devez apprendre de nouvelles langues et de nouvelles façons d'exécuter des tâches. Le faire simplement à l’aide d’une calculatrice n’est pas la bonne façon de procéder.

Et je sais que ceci est un message dans un vieux fil de discussion, mais il apparaît toujours dans les résultats de Google:)

En code (PHP), j’ai trouvé la solution la plus rapide:

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

Oui, c'est une pièce modifiée du CMS. La raison principale est plus rapide parce que, lorsque vous lisez la question, ils indiquent déjà que le nombre le plus bas possible pour les 10 premiers entiers est 2520. Pour cette raison, vous pouvez simplement incrémenter de 2520 au lieu de 20. Vous obtenez ainsi 126 fois moins de boucles

Answer 8

Je sais que vous avez dit PHP, mais voici mon brouillon en 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)

Ce n’est pas aussi élégant que je l’aurais pu, mais il calcule le plus petit commun multiple des nombres de 2 à 2 000 sur 15s. Si votre solution itérative pouvait traiter un milliard de candidats par seconde, il faudrait 10 ^ 849 ans pour terminer.

En d'autres termes, ne vous préoccupez pas d'optimiser le mauvais algorithme.