Le plus petit nombre qui est uniformément divisible par tous les nombres de 1 à 20?

Compte tenu du maximum N code>, vous souhaitez renvoyer le plus petit numéro qui est divisé par 1 à 20.

Regardons l'ensemble de 1 à 20. Tout d'abord, il contient un nombre de nombres premiers, nommément: p> xxx pré>

Ainsi, car il doit être divisé par 19, vous ne pouvez vérifier que des multiples de 19, car 19 est un nombre premier. Après cela, vous vérifiez si cela peut être divisé par celui ci-dessous, etc. Si le nombre peut être divisé par tous les nombres premiers avec succès, il peut être divisé par les chiffres 1 à 20. P>

float primenumbers[] = { 19, 17, 13, 11, 7, 5, 3, 2; };

float num = 20;

while (1)
{
   bool dividable = true;
   for (int i = 0; i < 8; i++)
   {
      if (num % primenumbers[i] != 0)
      {
         dividable = false;
         break;
      }
   }

   if (dividable) { break; }
   num += 1;
}

std::cout << "The smallest number dividable by 1 through 20 is " << num << std::endl;

voir http://fr.wikipedia.org/wiki/greatest_common_divisor Compte tenu de deux nombres A et B, vous pouvez calculer GCD (A, B) et le plus petit nombre divisible par les deux est un * B / GCD (A, B). La chose évidente alors de faire est de conserver une sorte de cycle de fonctionnement et d'ajouter les chiffres que vous vous souciez d'un par un: vous avez une réponse jusqu'à présent A et vous ajoutez dans le numéro suivant X_I à considérer en mettant

a '= A * X_I / (GCD (A, X_I))

Vous pouvez voir que cela fonctionne réellement en considérant ce que vous obtenez si vous mettez en compte tout et écrivez comme des produits de nombres premiers. Cela devrait à peu près vous permettre de déterminer la réponse à la main.

facteur tous les entiers de 1 à 20 dans leurs factorisations primordiales. Par exemple, le facteur 18 comme 18 = 3 ^ 2 * 2. Maintenant, pour chaque numéro de choix P code> qui apparaît dans la factorisation principale de certains entier compris entre 1 et 20, trouvez l'exposant maximal qu'il contient a parmi toutes ces factorisations primordiales. Par exemple, le premier 3 code> aura l'exposant 2 code> car il apparaît dans la factorisation de 18 comme 3 ^ 2 et s'il est apparu dans une factorisation principale avec un exposant de 3 ( C'est-à-dire 3 ^ 3), ce nombre devrait être au moins aussi grand que 3 ^ 3 = 27 qu'il en dehors de la plage 1 à 20. Récupérez maintenant tous ces nombres premiers avec leur exposant correspondant et vous avez la réponse. Ainsi, à titre d'exemple, trouvons le plus petit nombre de manière uniformément divisible par tous les nombres de 1 à 4. p> xxx pré>

Les nombres premiers apparaissant sont 2 code > et 3 code>. Nous notons que l'exposant maximum de 2 code> est 2 code> et l'exposant maximal de 3 code> est 1 code>. Ainsi, le plus petit numéro qui est uniformément divisible par tous les nombres de 1 à 4 est 2 ^ 2 * 3 = 12. P>

Voici une implémentation relativement simple. P>

Enter an integer: 20
Answer: 232792560

Le plus petit numéro divisible par deux numéros est le LCM de ces deux numéros. En fait, le plus petit nombre divisible par un ensemble de n chiffres x1..xn est le LCM de ces nombres. Il est facile de calculer le LCM de deux nombres (voir l'article Wikipedia) et vous pouvez étendre aux n chiffres en exploitant le fait que xxx

Remarque: méfiez-vous des débordements.

code (en python): xxx

indice:

Au lieu d'incrémenter num par 1 à chaque étape, vous pouvez l'incrémenter de 20 (fonctionnera beaucoup plus rapidement). Bien sûr, il peut également y avoir d'autres améliorations, y penserai plus tard si j'ai le temps. J'espère que je vous ai aidé un peu.

Il y a un moyen plus rapide de répondre au problème, en utilisant la théorie des numéros. D'autres réponses contiennent des indications comment faire cela. Cette réponse est uniquement à propos d'une meilleure façon d'écrire le si condition dans votre code d'origine.

Si vous souhaitez seulement remplacer la longue condition, vous pouvez l'exprimer plus bien en une boucle: < / p> xxx

devient: xxx

Le style n'est pas génial mais je pense que c'est ce que vous cherchiez.