Somme des nombres premiers inférieurs à $P^2$

Fly77
Modifié (August 2024) dans Shtam

Bonjour,

Je me suis amusé à créer un programme Python avec l'aide de GPT, qui calcule la somme des nombres premiers inférieurs à $$P^2$$. Le programme n'additionne pas simplement les nombres premiers de 2 jusqu'à $$P^2$$, mais utilise une approche différente en intégrant la somme de Gauss pour optimiser le calcul.

Je ne sais pas si c'est plus rapide que les méthodes traditionnelles, car la quantité de combinaisons de nombres premiers augmente rapidement.

Pour de petits nombres, il est possible de comprendre l'algorithme, car le programme Python détaille les calculs intermédiaires.

Merci,

Thomas.

from itertools import combinations

from math import ceil, floor


def is_prime(num):

    """Check if a number is prime."""

    if num <= 1:

        return False

    if num <= 3:

        return True

    if num % 2 == 0 or num % 3 == 0:

        return False

    i = 5

    while i * i <= num:

        if num % i == 0 or num % (i + 2) == 0:

            return False

        i += 6

    return True


def generate_n_primes(n):

    """Generate a list of the first n prime numbers."""

    primes = []

    num = 2

    while len(primes) < n:

        if is_prime(num):

            primes.append(num)

        num += 1

    return primes


def calculate_custom_sum(pn_squared, combination):

    """Calculate the custom sum using the given formula."""

    product_combination = 1

    for number in combination:

        product_combination *= number


    # Calculate floor value

    floor_val = floor(pn_squared / product_combination)


    # Calculate max_min_ratio for multiple elements

    if len(combination) > 1:

        max_min_ratio = combination[-1]

        for i in range(len(combination) - 2, -1, -1):

            max_min_ratio /= combination[i]

    else:

        max_min_ratio = combination[0]


    # Apply the formula

    sum_value = product_combination * (

        (floor_val * (floor_val + 1) // 2) - ((ceil(max_min_ratio) - 1) * ceil(max_min_ratio) // 2)

    )


    # Determine sign based on the number of elements in the combination

    if len(combination) % 2 == 0:

        sum_value *= 1  # Positive for even

    else:

        sum_value *= -1  # Negative for odd


    return sum_value, max_min_ratio


def print_prime_combinations(primes, pn_squared):

    """Print combinations of primes from 1 to n along with the custom sum formula."""

    total_sum = 0

    for k in range(1, len(primes) + 1):

        primes_list_str = ', '.join(map(str, primes))

        print(f"[{primes_list_str}] Parmi {k}:")

        combs = combinations(primes, k)

        for comb in combs:

            custom_sum, max_min_ratio = calculate_custom_sum(pn_squared, comb)

            product_combination = 1

            for number in comb:

                product_combination *= number


            # Determine the correct ratio for printing

            if len(comb) > 1:

                ratio_str = "÷".join(map(str, reversed(comb)))

            else:

                ratio_str = f"{comb[0]}"


            # Print the result with the appropriate formula and value

            sign = "-" if len(comb) % 2 == 1 else ""

            print(f"{comb}: {sign}{product_combination}*(⌊{pn_squared}/{product_combination}⌋*(⌊{pn_squared}/{product_combination}⌋+1)/2-(⌈{ratio_str}⌉-1)*⌈{ratio_str}⌉/2) = {custom_sum}")

            total_sum += custom_sum

        print()

    return total_sum


if __name__ == "__main__":

    n = int(input("Entrez le nombre de nombres premiers à générer (p(n)): "))

    

    # Generate the first n prime numbers

    prime_list = generate_n_primes(n)

    

    # Calculate the square of the last prime number

    pn_squared = prime_list[-1] ** 2

    

    # Calculate the sum of integers from 1 to pn_squared - 1

    sum_of_integers = (pn_squared * (pn_squared - 1)) // 2 - 1


    # Print the square of the last prime number and the sum of integers

    print(f"\np({n})^2 est {prime_list[-1]}^2 = {pn_squared}.")

    print(f"La somme des entiers de 1 à {pn_squared} moins 1 est {pn_squared}({pn_squared}-1)/2-1={sum_of_integers}.\n")

    

    # Print combinations with the custom sum formula

    total_custom_sum = 0

    if n > 1:

        total_custom_sum = print_prime_combinations(prime_list[:-1], pn_squared)


    # Calculate and print the sum of primes less than pn_squared

    sum_of_primes_less_than_pn_squared = sum_of_integers + total_custom_sum

    print(f"La somme des nombres premiers inférieur à {pn_squared} est {sum_of_integers}{total_custom_sum:+}={sum_of_primes_less_than_pn_squared}")


Réponses

  • Je te l'ai déjà dit... mais l'apprentissage naît de la répétition : sur ce forum, tu peux utiliser le formatage "Code" en cliquant sur le caractère ¶ puis sur "Code" et en tapant ton code.
    Si tu veux le copier-coller, il faut rajouter une étape après avoir appuyé sur "Code", tu bascules en mode HTML en cliquant sur </> et tu colles ton code entre les balises <code> et </code>.

    Ton code sera ainsi plus lisible et donc susceptible d'être lu.

    Ceci étant dit, ta méthode ultra naïve de calculs des nombres premiers n'a aucune chance d'être performante... et ton programme mettra des heures si on lui demande ne serait-ce que le 1000ème nombre premier alors qu'un simple crible d'Érathostène donnerait la réponse instantanément.
    Par ailleurs, il y a des centaines d'affichages intermédiaires inutiles qui ralentissent d'autant plus le calcul !
  • Fly77
    Modifié (August 2024)
    Comme ça?
    J'utilise le crible d'Ératosthène, mais comme j'additionne les nombres, il y a des chevauchements entre les multiples de 2 et de 3, ce qui m'oblige à corriger cette erreur en ajoutant les multiples de 2 * 3, et ainsi de suite. Le crible d'Ératosthène ne fait qu'éliminer les nombres non premiers, il n'additionne pas. Éliminer plusieurs fois le même nombre avec le crible d'Ératosthène ne pose pas de problème, mais avec ma méthode, il est nécessaire d'apporter des corrections.
    from itertools import combinations
    
    from math import ceil, floor
    
    
    
    def is_prime(num):
    
        """Check if a number is prime."""
    
        if num <= 1:
    
            return False
    
        if num <= 3:
    
            return True
    
        if num % 2 == 0 or num % 3 == 0:
    
            return False
    
        i = 5
    
        while i * i <= num:
    
            if num % i == 0 or num % (i + 2) == 0:
    
                return False
    
            i += 6
    
        return True
    
    
    
    def generate_n_primes(n):
    
        """Generate a list of the first n prime numbers."""
    
        primes = []
    
        num = 2
    
        while len(primes) < n:
    
            if is_prime(num):
    
                primes.append(num)
    
            num += 1
    
        return primes
    
    
    
    def calculate_custom_sum(pn_squared, combination):
    
        """Calculate the custom sum using the given formula."""
    
        product_combination = 1
    
        for number in combination:
    
            product_combination *= number
    
    
    
        # Calculate floor value
    
        floor_val = floor(pn_squared / product_combination)
    
    
    
        # Calculate max_min_ratio for multiple elements
    
        if len(combination) > 1:
    
            max_min_ratio = combination[-1]
    
            for i in range(len(combination) - 2, -1, -1):
    
                max_min_ratio /= combination[i]
    
        else:
    
            max_min_ratio = combination[0]
    
    
    
        # Apply the formula
    
        sum_value = product_combination * (
    
            (floor_val * (floor_val + 1) // 2) - ((ceil(max_min_ratio) - 1) * ceil(max_min_ratio) // 2)
    
        )
    
    
    
        # Determine sign based on the number of elements in the combination
    
        if len(combination) % 2 == 0:
    
            sum_value *= 1  # Positive for even
    
        else:
    
            sum_value *= -1  # Negative for odd
    
    
    
        return sum_value, max_min_ratio
    
    
    
    def print_prime_combinations(primes, pn_squared):
    
        """Print combinations of primes from 1 to n along with the custom sum formula."""
    
        total_sum = 0
    
        for k in range(1, len(primes) + 1):
    
            primes_list_str = ', '.join(map(str, primes))
    
            print(f"[{primes_list_str}] Parmi {k}:")
    
            combs = combinations(primes, k)
    
            for comb in combs:
    
                custom_sum, max_min_ratio = calculate_custom_sum(pn_squared, comb)
    
                product_combination = 1
    
                for number in comb:
    
                    product_combination *= number
    
    
    
                # Determine the correct ratio for printing
    
                if len(comb) > 1:
    
                    ratio_str = "÷".join(map(str, reversed(comb)))
    
                else:
    
                    ratio_str = f"{comb[0]}"
    
    
    
                # Print the result with the appropriate formula and value
    
                sign = "-" if len(comb) % 2 == 1 else ""
    
                print(f"{comb}: {sign}{product_combination}*(⌊{pn_squared}/{product_combination}⌋*(⌊{pn_squared}/{product_combination}⌋+1)/2-(⌈{ratio_str}⌉-1)*⌈{ratio_str}⌉/2) = {custom_sum}")
    
                total_sum += custom_sum
    
            print()
    
        return total_sum
    
    
    
    if __name__ == "__main__":
    
        n = int(input("Entrez le nombre de nombres premiers à générer (p(n)): "))
    
        
    
        # Generate the first n prime numbers
    
        prime_list = generate_n_primes(n)
    
        
    
        # Calculate the square of the last prime number
    
        pn_squared = prime_list[-1] ** 2
    
        
    
        # Calculate the sum of integers from 1 to pn_squared - 1
    
        sum_of_integers = (pn_squared * (pn_squared - 1)) // 2 - 1
    
    
    
        # Print the square of the last prime number and the sum of integers
    
        print(f"\np({n})^2 est {prime_list[-1]}^2 = {pn_squared}.")
    
        print(f"La somme des entiers de 1 à {pn_squared} moins 1 est {pn_squared}({pn_squared}-1)/2-1={sum_of_integers}.\n")
    
        
    
        # Print combinations with the custom sum formula
    
        total_custom_sum = 0
    
        if n > 1:
    
            total_custom_sum = print_prime_combinations(prime_list[:-1], pn_squared)
    
    
    
        # Calculate and print the sum of primes less than pn_squared
    
        sum_of_primes_less_than_pn_squared = sum_of_integers + total_custom_sum
    
        print(f"La somme des nombres premiers inférieur à {pn_squared} est {sum_of_integers}{total_custom_sum:+}={sum_of_primes_less_than_pn_squared}")
    
    
  • C'est déjà bien plus lisible, mais tu aurais pu également supprimer toutes les lignes vides (soit une ligne sur deux !).

    Quant au crible d'Ératosthène, tu ne sembles pas le connaître correctement. Le principe est de découvrir les nombres premiers au fur et à mesure de l'avancée et de barrer leurs multiples pour ne garder que les valeurs non barrées. Il ne reste plus qu'à faire la somme des nombres barrés pour achever le calcul.
    En terme de complexité, on obtient quelque chose en $\mathcal{O}(N\ln(\ln(N)))$ où $N$ est le nombre jusqu'auquel tu effectues le crible.
    Puisque tu tiens à faire cette somme jusqu'au carré du $n$-ème nombre premier $p_n^2$ et que $p_n=\Theta(n\ln(n))$, on obtient une complexité en $\mathcal{O}(n^2\ln^2(n)\ln(\ln(n)))$ où $n$ est le numéro du nombre premier que tu demandes au départ.

    Ce n'est PAS DU TOUT ce que tu fais.
    Toi, tu testes chaque nombre en le divisant par les précédents pour savoir s'il est premier... et ensuite tu traites chaque produit formé d'un nombre quelconque de premiers...
    Le nombre d'opérations que tu fais est de l'ordre de $2^n$ puisque tu fais la liste de toutes les combinaisons d'éléments pris parmi les $n$ premiers nombres premiers et comme tu as testé à chaque fois de façon naïve pour savoir si un nombre est premier, on obtient finalement une complexité de l'ordre de $\mathcal{O}(2^nn^2\ln^2(n))$.

    Pour $n=25$, avec ta méthode, j'ai dû arrêter Python après plus de 8h de calculs sans qu'il ait fini.
    Avec le crible d'Ératosthène, le résultat prend moins d'un dixième de seconde.

    Bref, je ne sais pas où tu veux en venir, mais ta méthode n'est pas du tout intéressante.
  • bisam a dit :
    Pour $n=25$, avec ta méthode, j'ai dû arrêter Python après plus de 8h de calculs sans qu'il ait fini.

    8h pour ça ?? Si tu ne sais pas quoi faire de ton processeur, j'ai une idée pour toi :) 

  • JLapin a dit :
    Si tu ne sais pas quoi faire de ton processeur, j'ai une idée pour toi :) 
    Pour moi c'est foutu, concernant mon processeur je lis : Avec la difficulté quotidienne actuelle, vous gagnerez 0 $, donc le retour sur investissement de i7 6700 est de 0 jours. 

  • @JLapin : Je l'ai mis à tourner avant d'aller manger, hier soir, et j'ai oublié de vérifié après le repas... donc il a tourné toute la nuit, pour rien.
  • J'ai demandé à GPT d'optimiser le calcul pour n = 25. Le calcul a pris 3,427284 secondes.

    thomas@GUITARD:~$ python3 '/home/thomas/Documents/1a.py' 25
    Entrez le nombre de nombres premiers à générer (p(n)): 25

    p(25)^2 est 97^2 = 9409.
    La somme des entiers de 1 à 9409 moins 1 est 9409(9409-1)/2-1=44259935.
    La somme des nombres premiers inférieur à 9409 est 44259935-39162923=5097012
    Le calcul a pris 3.427284 secondes.

    from itertools import combinations
    from math import ceil, floor, prod
    import time  # Import du module time pour mesurer la durée
    
    def is_prime(num):
        """Check if a number is prime."""
        if num <= 1:
            return False
        if num <= 3:
            return True
        if num % 2 == 0 or num % 3 == 0:
            return False
        i = 5
        while i * i <= num:
            if num % i == 0 or num % (i + 2) == 0:
                return False
            i += 6
        return True
    
    def generate_n_primes(n):
        """Generate a list of the first n prime numbers."""
        primes = []
        num = 2
        while len(primes) < n:
            if is_prime(num):
                primes.append(num)
            num += 1
        return primes
    
    def calculate_custom_sum(pn_squared, combination):
        """Calculate the custom sum using the given formula."""
        product_combination = prod(combination)
    
        # Calculate floor value
        floor_val = floor(pn_squared / product_combination)
    
        # Calculate max_min_ratio for multiple elements
        max_min_ratio = combination[-1] / prod(combination[:-1]) if len(combination) > 1 else combination[0]
    
        # Apply the formula
        sum_value = product_combination * (
            (floor_val * (floor_val + 1) // 2) - ((ceil(max_min_ratio) - 1) * ceil(max_min_ratio) // 2)
        )
    
        # Determine sign based on the number of elements in the combination
        if len(combination) % 2 != 0:
            sum_value *= -1  # Negative for odd
    
        return sum_value
    
    def compute_prime_combinations_sum(primes, pn_squared):
        """Compute the sum of custom sums for combinations of primes."""
        total_sum = 0
        for k in range(1, len(primes) + 1):
            for comb in combinations(primes, k):
                product_combination = prod(comb)
                if product_combination > pn_squared:
                    continue  # Skip calculations if the product is greater than pn_squared
    
                custom_sum = calculate_custom_sum(pn_squared, comb)
                if custom_sum == 0:
                    continue  # Skip adding zero results to the total sum
    
                total_sum += custom_sum
    
        return total_sum
    
    if __name__ == "__main__":
        n = int(input("Entrez le nombre de nombres premiers à générer (p(n)): "))
    
        start_time = time.time()  # Capture le temps de début
    
        # Generate the first n prime numbers
        prime_list = generate_n_primes(n)
    
        # Calculate the square of the last prime number
        pn_squared = prime_list[-1] ** 2
    
        # Calculate the sum of integers from 1 to pn_squared - 1
        sum_of_integers = (pn_squared * (pn_squared - 1)) // 2 - 1
    
        # Compute the total custom sum for prime combinations
        total_custom_sum = 0
        if n > 1:
            total_custom_sum = compute_prime_combinations_sum(prime_list[:-1], pn_squared)
    
        # Calculate the sum of primes less than pn_squared
        sum_of_primes_less_than_pn_squared = sum_of_integers + total_custom_sum
    
        end_time = time.time()  # Capture le temps de fin
    
        # Print the results and the time taken
        print(f"\np({n})^2 est {prime_list[-1]}^2 = {pn_squared}.")
        print(f"La somme des entiers de 1 à {pn_squared} moins 1 est {pn_squared}({pn_squared}-1)/2-1={sum_of_integers}.")
        print(f"La somme des nombres premiers inférieur à {pn_squared} est {sum_of_integers}{total_custom_sum:+}={sum_of_primes_less_than_pn_squared}")
    
        # Affichage du temps écoulé
        print(f"Le calcul a pris {end_time - start_time:.6f} secondes.")
    

  • Voici ce que cela peut donner avec le crible d'Ératosthène, et sans optimisation.
    import time
    from math import log       
    
    def intsqrt(n: int) -> int:
        """Calcule la racine carrée entière de n, 
        c'est-à-dire l'unique entier r tel que r²<=n<(r+1)²
        à l'aide de l'algorithme de Héron."""
        
        x = n
        while x**2 > n:
            x = x//2 + (n+x if x%2 else n) // (2*x)
        return x
    
    def eratho(N: int) -> list[bool]:
        """Renvoie une liste de booléens décrivant si l'entier k
        est premier ou non, par la méthode du crible d'Érathosthène"""
    
        #On initialise une liste de booléens, en éliminant d'office les pairs
        t = [False, False, True] + [i % 2 == 1 for i in range(3, N+1)]
        r = intsqrt(N)
        i = 3
        while i <= r:
            if t[i]: #si i est premier, on élimine ses multiples plus grands que i^2
                for j in range(i**2, N, i): 
                    t[j] = False 
            i += 2
        return t
    
    def primes_sum(n: int) -> int:
        """Renvoie la somme des nombres premiers inférieurs strictement 
        au carré du n-ème nombre premier p_n"""
        
        small_primes = [2,3,5,7,11]
        if n < 6:
            p_n = small_primes[n-1]
            isprime = eratho(121)
        else:
            N = int(n*log(n*log(n))) #N > p_n d'après Rosser
            isprime = eratho(N**2)
            nb_primes = 0
            for i in range(N):
                if isprime[i]:
                    nb_primes += 1
                    if nb_primes == n:
                        p_n = i
                        break
        print(f"Le {n}-ème nombre premier est {p_n}.")
        return sum(a for a in range(p_n**2) if isprime[a])
    
    if __name__ == "__main__":
        n = int(input("Entrez le nombre de nombres premiers à générer : "))
    
        start_time = time.time()  # Capture le temps de début
        
        # Print the results and the time taken
        s = primes_sum(n)
        print(f"La somme des nombres premiers inférieurs au carré de ce nombre est {s}.")
        end_time = time.time()  # Capture le temps de fin
    
        # Affichage du temps écoulé
        print(f"Le calcul a pris {end_time - start_time:.6f} secondes.")
    
    Pour n=25 et même n=35, le calcul est trop rapide pour être mesuré par "time".
    Pour n=100, il prend entre 6 et 8 centièmes de seconde.
    Pour n=1000, il prend 27s. On perd un peu de temps parce qu'on calcule plus de nombres premiers que nécessaires par le crible, pour ne le faire qu'une seule fois, afin de trouver d'une part $p_n$ et d'autre part tous les nombres premiers jusqu'à $p_n^2$.

    Il est probable qu'on puisse faire beaucoup mieux... mais c'est déjà des millions de fois plus rapide que ce que tu fais. Alors, je repose ma question : qu'espères-tu obtenir, et aussi pourquoi fais-tu ce calcul ?
  • J'avais remarqué qu'il était possible de calculer de cette manière et je souhaitais simplement le partager pour voir si cela pouvait susciter de l'intérêt.
Connectez-vous ou Inscrivez-vous pour répondre.