Projet Euler # 5; cette solution fonctionne – mais pourquoi?

Le problème 5 du projet Euler est ainsi libellé: “2520 est le plus petit nombre pouvant être divisé par chacun des nombres compris entre 1 et 10 sans rest.

Quel est le plus petit nombre positif divisible par tous les nombres de 1 à 20? “Voici le code c ++ de la fonction que j’utilise.

long long unsigned int rangeLCM(int n) { long long unsigned int ans=1; for(int i=1;i<=n;i++) { if(ans%i!=0) { if(i%(ans%i)==0)ans*=(i/(ans%i)); else ans*=i; } } return ans; }

Le code fonctionne bien pour l’exemple rangeLCM(10)=2520 dans le problème et le problème lui-même { rangeLCM(10)=2520 et rangeLCM(20)=232792560 }, mais je pense que ce n’est pas parfait et manque certains cas rangeLCM(20)=232792560 .

Au lieu de calculer réellement le LCM(ans,i) , j’ai vérifié que le plus gros des deux (toujours ans ) est divisible par i . Dans le cas contraire, alors ans est multiplié par un nombre égal à i/(ans%i) ou i selon que i est divisible par (ans%i) ou non.

Ceci est basé sur les faits suivants:

 LCM(8,12)=24=12*(8/(12%8)); LCM(9,30)=90=30*(9/(30%9) LCM(7,13)=91=13*7

Cependant, il échoue pour les types de cas suivants: LCM(8,14)=56 != 8*14

Pourtant, le code de rangeLCM donne le bon résultat pour toutes les entrées que j’ai déjà essayées. Pourquoi?

Votre logique ne fonctionne pas

  if(i%(ans%i)==0)ans*=(i/(ans%i)); else ans*=i;

Par exemple, si ans = 10 et i = 14 , le lcm doit être égal à 70, mais dans votre code, il est égal à 140.

La raison en est que, entre ans et i , il existe des diviseurs communs, mais votre code ne peut pas le détecter.

Pour expérimenter, j’ai écrit un petit morceau de code à vérifier avec Java.

 class Solution { public static void main(Ssortingng[] args) { long ans = 1; for (long i = 1; i <= 40; i++) { if (ans % i != 0) { long before = (ans*i/gcd(ans,i)); if (i % (ans % i) == 0){ ans *= (i / (ans % i)); }else{ ans *= i; } System.out.println(ans + " " + before + " " + i); } } } public static long gcd(long a, long b) { if (b == 0) { return a; } return gcd(b, a % b); } }

Sortie

 2 2 2 6 6 3 12 12 4 60 60 5 420 420 7 840 840 8 2520 2520 9 27720 27720 11 360360 360360 13 720720 720720 16 12252240 12252240 17 232792560 232792560 19 5354228880 5354228880 23 26771144400 26771144400 25 722820898800 80313433200 27 20961806065200 20961806065200 29 649815988021200 649815988021200 31 1299631976042400 1299631976042400 32 48086383113568800 48086383113568800 37

Quand i = 27, il y a une différence entre la bonne réponse et la bonne réponse

La formule pour lcm (a, b) est

 lcm(a,b) = a*b/gcd(a,b)

Avec gcd est le plus grand commun diviseur entre deux nombres a et b

Je pense que vous manquez beaucoup de cas, vous devez mettre en œuvre l’algorithme euclidien à

 if(i%(ans%i)==0)ans*=(i/(ans%i));