Voici un résumé de l'énoncé du problème 10 "Summation of primes" du Project Euler (traduction complète en français ici) :

Find the sum of all the primes below two million.

Compréhension du problème

Reformulons le problème : il nous faut trouver la somme de tous les nombres premiers inférieurs à 2 millions. Pour résoudre ce problème, il y a 2 solutions possibles :

• Soit faire un programme brute force qui testera tous les nombres impairs, plus 2, un par un pour savoir s'ils sont premiers
• Soit utiliser un crible comme celui d'Ératosthène ou d'Atkin qui permettent, au fur et à mesure des nombres testés, de trouver les nombres qui sont premiers et d'en déduire les nombres qui ne le sont, c'est à dire tous les multiples des nombres premiers trouvés

Le programme

Voici donc les 2 programmes Python (1 pour chaque solution) que nous pouvons utiliser pour résoudre ce problème :

• 1er programme (solution 1) :

  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
  resultat = 2
  divisors = []
  for i in range(3, 2000000, 2):    
      if is_prime(i):
          resultat += i
  print(resultat)

• 2nd programme (solution 2) :

  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]
  print(sum(primes_below(2000000)))

Vous remarquerez que le 2nd programme va environ 50 fois plus vite que le 1er, le second programme mettant moins d'1 seconde pour afficher le résultat alors que le premier plus de 50.

Je n'ai pas d'autres explications à donner si ce n'est que le fonctionnement des fonctions \(\text{is_prime}\) et \(\text{primes_below}\) est explicité dans cet article.

Le résultat

La réponse à ce problème est 142913828922.