Problème 1

Si on liste tous les entiers naturels inférieurs à 20 qui sont multiples de 5 ou de 7, on obtient 5, 7, 10, 14 et 15. La somme de ces nombres est 51.

Trouvez la somme de tous les multiples de 5 ou de 7 inférieurs à 2013.

Commentaire

Les multiples de 35 sont multiples de 5 et de 7. Selon l'algorithme choisi, il faudra éviter de les prendre en compte deux fois.

A la place de l'algorithme ci-dessous, on aurait pu utiliser la formule de la somme des n premiers termes d'une suite arithmétique.

Algorithme

Faire la somme de tous les multiples de 5, de 5 à 2012.
Faire la somme de tous les multiples de 7, de 7 à 2012.
Faire la somme de tous les multiples de 35, de 35 à 2012.
La solution est : somme des multiples de 5 + somme des multiples de 7 - somme des multiples de 35.

Codé avec la version 7.2.6.2 (x64) de LibreOffice

sub probleme_001(m1 as long,m2 as long,limite as long,resultat as long)

  'resultat retourne la somme des multiples de m1 ou m2 dans l'intervalle [1;limite].
  'm1 et m2 doivent être des nombres premiers.
  
  dim i  as long
  dim m3 as long
  dim s1 as long
  dim s2 as long
  dim s3 as long
  
  m3=m1*m2
  for i=m1 to limite step m1
     s1=s1+i
  next i
  for i=m2 to limite step m2
     s2=s2+i
  next i     
  for i=m3 to limite step m3
     s3=s3+i
  next i
  resultat=s1+s2-s3   
end sub     

Problème 2

Chaque nouveau terme de la suite de Fibonacci est généré en ajoutant les deux termes précédents. En commençant avec 1 et 1, les 10 premiers termes sont les suivants : 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

En prenant en compte les termes de la suite de Fibonacci dont les valeurs ne dépassent pas 4 millions, trouver la somme des termes impairs.

Commentaire

Un nombre entier est pair si le reste de la division par 2 vaut 0, c'est à dire si nombre modulo 2 = 0.

Algorithme

Initialiser la valeur du premier terme de la suite de fibonacci à 1.
Initialiser la valeur du précédent terme de la suite de fibonacci à 0.
Répéter :
  Si la valeur du terme est impaires, l'additionner dans un compteur.
  Conserveur la valeur du terme actuel en tant que valeur précédente.
  Calculer la valeur du terme suivant.
Jusqu'à ce que la valeur soit supérieure à la limite.
La solution est la valeur du compteur au sortir de la boucle.

Codé avec la version 7.2.6.2 (x64) de LibreOffice

sub probleme_002(limite as long,resultat as long)

  'resultat retourne la somme des termes impairs de la suite de Fibonacci dans l'intervalle [1;limite].

  dim aux       as long
  dim nombre    as long
  dim precedent as long

  nombre=1
  precedent=0
  resultat=0
  if limite>0 then
    do
      if (nombre mod 2)>0 then resultat=resultat+nombre
      aux=precedent
      precedent=nombre
      nombre=nombre+aux 
    loop until nombre>limite
  end if  
end sub

Problème 3

Les facteurs premiers du nombre 2013 sont 3, 11 et 61 car 3x11x61=2013.

Quel est le plus grand facteur premier du nombre 20130101 ?

Commentaire

Pour trouver le plus grand facteur premier d'un nombre entier positif, il faut décomposer ce nombre en nombres premiers.

Cette décomposition se fait en partant du plus petit nombre premier comme diviseur, c'est à dire 2. Il s'agit de procéder à des divisions euclidiennes successives donnant un reste à 0. Tant que le quotient obtenu est divisible par le nombre premier, on poursuit. Sinon on passe au nombre premier immédiatement supérieur. Le plus grand facteur premier est trouvé (il s'agit du dernier diviseur) lorsque le quotient vaut 1.

L'algorithme est optimisé en prenant en compte les deux particularités suivantes :

• Un entier supérieur à 1 est un nombre premier s'il est divisible par 1 et par lui-même. Il est inutile de chercher un diviseur au delà de la racine carré de cet entier.
• 2 est le seul nombre premier pair.

Algorithme

Répéter :
 Rechercher le plus petit nombre premier diviseur du nombre tel que nombre modulo nombre premier = 0.
 nombre ← nombre / nombre premier.
Jusqu'à ce que le quotient de la division euclidienne vaille 1.
La solution est le dernier nombre premier diviseur de nombre.

Codé avec la version 7.6.7.2 (x64) de LibreOffice

sub probleme_003(ByVal nombre as long,resultat as long)

  'resultat retourne le plus grand facteur premier d'un nombre positif
  
  dim aux      as long
  dim diviseur as long
  dim limite   as long
  
  if nombre>1 then
    do   
      '-> Début de la recherche du plus petit nombre premier diviseur de nombre
      diviseur=0        
      if (nombre mod 2)=0 then diviseur=2 else if (nombre mod 3)=0 then diviseur=3
      if diviseur=0 then
        aux=3
        limite=int(sqr(nombre))  
        while (diviseur=0) and (aux<limite)  
            aux=aux+2
            if (nombre mod aux)=0 then diviseur=aux
        wend
      end if
      '<- Fin de la recherche
      if diviseur=0 then diviseur=nombre   'Nombre est premier car aucun diviseur trouvé
      nombre=nombre/diviseur
    loop until nombre=1                    'Boucle tant qu'il reste un diviseur autre que 1
    resultat=diviseur
  end if  
end sub