Comme il est possible, dans les différents problèmes du Project Euler, d'avoir besoin d'utiliser plusieurs fois le même code/fonction, je répertorie et explique ici ces codes pour ne pas avoir à le faire dans les différents articles où j'expose mes solutions trouvées aux problèmes.

Obtenir la liste des diviseurs/facteurs d'un nombre

Cette fonction permet d'obtenir tous les diviseurs/facteurs d'un nombre en incluant ou pas dans cette liste 1 et le nombre :

def divisors(nb, extremum = False):
    divisors = []
    inf = 1 if extremum else 2
    for i in range(inf, int(nb**0.5)+1):
        q, r = divmod(nb, i)
        if r == 0:
            if q >= i:
                divisors.append(i)
                if q > i:
                    divisors.append(nb//i)
    return divisors

Exemples :

• \(\text{divisors}(10)\) retourne \([2, 5]\)
• \(\text{divisors}(10, True)\) retourne \([1, 10, 2, 5]\)

Explications :

• Si on sait que \(a\) est divisible par \(b\) et que \(a/b = c\), alors \(a/c = b\), ce qui veut dire que si 10 est divisible par 2, alors nous pouvons en déduire qu'il est divisible par 5 car \(10/2 = 5\)
• Si nous connaissons tous les facteurs d'un nombre inférieurs à sa racine carrée, alors nous pouvons en déduire le reste de ses diviseurs. Prenons 36 comme exemple. 36 est divisible par 2, \(36/2 = 18\) et donc divisible par 18, il est divisible par 3, \(36/3 = 12\), et donc par 12, il est divisible par 4, \(36/4 = 39\) et donc par 9. Nous pouvons constater que plus on divise 36 par un nombre proche de sa racine et plus le résultat obtenu est proche de sa racine aussi. Si nous continuons donc, 36 est divisible par 6, \(36/6 = 6\), puis par 9, \(36/9 = 4\), diviseur que nous avions déjà obtenu en divisant 36 par un nombre inférieur à sa racine, 4.

Vérifier si un nombre est premier

Cette fonction permet de vérifier si un nombre est premier :

def is_prime(nb):
    if nb == 1:
        return False
    if nb == 2:
        return True
    elif nb%2 == 0:
        return False
    for i in range(3, int(nb**0.5)+1, 2):
        if nb%i == 0:
            return False
    return True

Exemples :

• \(\text{is_prime}(17)\) retourne \(\text{True}\)
• \(\text{is_prime}(18)\) retourne \(\text{False}\)

Explications :

• Si un nombre n'est divisible par aucun des nombres inférieurs à sa racine carrée ou égal si la racine est entière, alors ce nombre est premier. Cela est du au même principe que la fonction précédente pour obtenir les diviseurs d'un nombre.
• Par soucis de rapidité, si un nombre n'est pas divisible par 2, il n'est divisible par aucun nombre pair, ce qui permet d'éliminer la moitié des divisions.

Vérifier si un nombre est un palindrome

Cette fonction permet de vérifier si un nombre est un palindrome, c'est à dire si on voit le même nombre quand on le lit de gauche à droite que droite à gauche :

def is_palindrome(nb):
    if str(nb) == str(nb)[::-1]:
        return True
    return False

Exemples :

• \(\text{is_palindrome}(11)\) retourne \(\text{True}\)
• \(\text{is_palindrome}(27)\) retourne \(\text{False}\)

Explication :

• on convertit le nombre en chaîne de caractère
• on regarde si la chaîne de caractères inversée est la même que celle d'origine

Obtenir la liste des nombres premiers inférieurs à un certain nombre

Cette fonction permet d'obtenir très rapidement la liste de tous les nombres premiers inférieurs à une certaine limite / certain nombre et est une implémentation améliorée du crible d'Ératosthène :

def primes_below(end):
    if end < 2:
        return []
    lng = (end//2) - 1
    primes = [True]*lng  
    for i in range(int(lng**0.5)):  
        if primes[i]:
            for j in range(2*i*(i + 3) + 3, lng, 2*i + 3):
                primes[j] = False  
    return [2] + [i*2 + 3 for i, j in enumerate(primes) if j]

Exemples :

• \(\text{primes_below}(10)\) retourne \([2, 3, 5, 7]\)
• \(\text{primes_below}(50)\) retourne \([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]\)

Explications :

• Imaginons que nous voulons trouver tous les nombres premiers inférieurs à 100. Nous savons que potentiellement il ne peut y avoir que \(50-1\) nombres premiers car tous les nombres pairs sauf 2 ne le sont pas. Créons donc une liste contenant 49 indexes dont leurs valeurs sont mises à vraies par défaut, ce qui veut dire que ces valeurs sont supposées correspondre à des nombres premiers.
• Prenons le premier index de cette liste qui correspond donc au nombre 3, premier nombre premier après 2, et passons à faux tous les indexes supérieurs à \(3^2\) et multiples de 3, mais pas de 2 (tous les multiples de 2 n'étant pas comptés), donc \(3\cdot 3\), \(3\cdot 5\), \(3\cdot 7\)... Une fois fait, nous savons que le prochain nombre premier supérieur à 3 est 5. Il nous faut donc refaire la même chose que pour 3, c'est à dire supprimer tous les indexes supérieurs à \(5^2\) et multiples de 5, mais pas de 2, donc \(5\cdot 5\), \(5\cdot 7\), \(5\cdot 9\)... Nous obtenons le prochain nombre premier et devons refaire encore la même chose pour ce nombre premier. Et ainsi de suite pour tous les nombres premiers inférieurs à la racine carrée de la limite, 10 dans notre cas, car si, par exemple, nous prenons 11, premier nombre premier supérieur à 10, \(11^2 > 100\).
• Une fois que l'on a la liste contenant tous les nombres premiers inférieurs à notre nombre limite, on la retourne.

Vérifier si un nombre est abondant

Cette fonction permet de vérifier si un nombre est abondant :

def is_abundant(n):
    return sum(divisors(n))+1 > n

Exemples :

• \(\text{is_abundant}(12)\) retourne \(\text{True}\)
• \(\text{is_abundant}(15)\) retourne \(\text{False}\)

Explications :

• Un nombre abondant est un nombre dont la somme de ses diviseurs (sans inclure lui-même) est supérieure au nombre lui-même
• La fonction se contente donc de faire la somme des diviseurs d'un nombre grâce à la fonction divisors (voir plus haut) et de la comparer à ce nombre