Accueil » Tutoriels » Python » PYTHON TD N°5
Compilation Python | Création de site internet
Compilation Python | Création de site internet

PYTHON TD N°5

Énoncé: Soit NN un entier strictement positif.
Quel est le plus petit entier strictement positif et divisible par tous les entiers de 11 à NN?

Remarque: l’énoncé original du Project Euler » se limite à N=20N=20.
Le résultat est alors 232792560232792560.

————————————————————————————————

Il s’agit bien sûr de calculer ici πN=ppcm(1,,N)πN=ppcm(1,…,N).

  1. Première solutionOn part de π1=1π1=1 et on utilise les relations πn=nπn1=nπn1nπn1πn=n∨πn−1=nπn−1n∧πn−1La solution la plus simple (mais pas la plus glorieuse) est d’importer la fonction gcd du modulefractions.

    Par acquis de conscience, on peut bien sûr redéfinir classiquement la fonction gcd, le reste étant inchangé:

  2. Deuxième solutionOn définit ici nos propres fonctions gcd et lcm, et on applique par associativité la fonction lcmaux éléments de {1,,N}{1,…,N} (utilisation de la fonction reduce du module functools).
  3. Troisième solutionPartant de π1=1π1=1, on a π2=2π1=2π2=2π1=2 (nouveau facteur premier 22), puis π3=3π2=6π3=3π2=6(nouveau facteur premier 33).Ensuite π4=2π3=12π4=2π3=12 (augmentation de la valuation du facteur premier 22), puis π5=5π4=60π5=5π4=60 (le facteur premier n=5n=5), puis π6=π5=60π6=π5=60 (pas d’augmentation dans l’exposant des facteurs premiers 22 et 33).

    Pour passer de πn1πn−1 à πnπn: si πnπn est (déjà) divisible par nn, on a πn=πn1πn=πn−1. Sinon c’est que nnintroduit une augmentation d’une unité dans l’exposant d’un facteur premier kk (et dans ce cas πn=kπn1πn=kπn−1).

À propos Amine MAGDICH

Animé par l'envie d'entreprendre, je déborde de curiosité pour le numérique et les nouvelles technologies. Sans cesse à la recherche de savoir, je pousse ma capacité d'apprentissage à son maximum, afin d'obtenir des compétences globales, répondant aux enjeux de la gestion humaine et technique d'un projet multimédia.

Laisser une réponse

x

Check Also

Compilation Python | Création de site internet

PYTHON TD N°4

Un entier naturel (écrit en base 1010) est un palindrome s’il se lit à l’identique ...

Compilation Python | Création de site internet

PYTHON TD N°3

Soit NN dans NN, avec N≥2N≥2. Écrire une fonction donnant le plus grand facteur premier ...