Lucas Willems

LUCAS WILLEMS

Un étudiant de 21 ans passionné par les maths et la programmation

English

Project Euler 27 : solution Python

Article

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

Find the product of the coefficients, \(a\) and \(b\), for the quadratic expression that produces the maximum number of primes for consecutive values of \(n\), starting with \(n = 0\).

Compréhension du problème

Reformulons le problème : il nous faut trouver le produit des coefficients a et b du polynôme \(P(n) = n^2 + an + b\) qui produit le plus grand nombre de nombres premiers pour des valeurs consécutives de n en commençant à \(n = 0\). La façon la plus simple, je pense, pour résoudre ce problème est alors de trouver le nombre de nombres premiers que produisent tous les polynômes pour \(a, b \in ]1000; 1000[\). Toutefois, par simple observation, nous pouvons réduire de manière conséquente cet intervalle car nous pouvons voir que :

Le programme

Voici donc le programme Python que nous pouvons utiliser :

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]
#Obtention de la liste des nombres premiers inférieurs à 1000
primes = primes_below(1000)
longest = 0
#b prend successivement la valeur des différents nombres premiers
for b in primes:
    #a prend successivement la valeur de tous les nombres impairs de -999 à 2
    for a in range(-999, 1000, 2):
        image = b
        n = 0
        #Calcul du nombre consécutif de nombres premiers
        while functions.is_prime(image):
            n += 1
            image = n**2 + a*n + b
        if n > longest:
            longest = n
            resultat = a*b
print(resultat)

Notez que ce programme utilise la fonction "primes_below" qui permet d'obtenir tous les nombres premiers inférieurs à un certain nombre. Cette fonction est explicitée dans cet article.

Le résultat

La réponse à ce problème est -59231.

Recherche

Voici les recherches relatives à cette page :

Commentaires

Qu'en pensez-vous ? Donnez moi votre avis (positif ou négatif) pour que je puisse l'améliorer.