Somme des nombres premiers inférieurs à $P^2$
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 ! -
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
-
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' 25Entrez le nombre de nombres premiers à générer (p(n)): 25p(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=5097012Le 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.
Bonjour!
Catégories
- 165.6K Toutes les catégories
- 64 Collège/Lycée
- 22.2K Algèbre
- 37.7K Analyse
- 6.3K Arithmétique
- 61 Catégories et structures
- 1.1K Combinatoire et Graphes
- 13 Sciences des données
- 5.1K Concours et Examens
- 26 CultureMath
- 51 Enseignement à distance
- 2.9K Fondements et Logique
- 10.8K Géométrie
- 86 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 79 Informatique théorique
- 3.9K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 29 Mathématiques et finance
- 343 Mathématiques et Physique
- 5K Mathématiques et Société
- 3.4K Pédagogie, enseignement, orientation
- 10.1K Probabilités, théorie de la mesure
- 804 Shtam
- 4.2K Statistiques
- 3.8K Topologie
- 1.4K Vie du Forum et de ses membres