Calculateur de nombres premiers

Calculateur de nombres premiers - Somme, comptage et recherche

🔢 Calculez la somme des nombres premiers, trouvez les nombres premiers dans un intervalle, vérifiez si un nombre est premier et trouvez le n-ième nombre premier. Algorithme rapide du crible d’Ératosthène avec visualisation.

Que sont les nombres premiers ?

Un nombre premier est un nombre naturel supérieur à 1 qui ne peut pas être obtenu en multipliant deux nombres naturels plus petits. Autrement dit, il possède exactement deux diviseurs : 1 et lui-même.

Les 25 premiers nombres premiers

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

Comment vérifier si un nombre est premier

Méthode 1 - Division d’essai :

• Vérifiez si n est divisible par un nombre de 2 à √n
• Si oui, il est composé (non premier)
• Si non, il est premier

Exemple : 17 est-il premier ?

• √17 ≈ 4,12, donc on teste 2, 3, 4
• 17 ÷ 2 = 8,5 (non divisible)
• 17 ÷ 3 = 5,67 (non divisible)
• 17 ÷ 4 = 4,25 (non divisible)
• Résultat : 17 est premier !

Crible d’Ératosthène

Algorithme ancien pour trouver tous les nombres premiers jusqu’à n :

• Étape 1 : Listez tous les nombres de 2 à n
• Étape 2 : Marquez 2 comme premier et barrez tous ses multiples
• Étape 3 : Prenez le prochain nombre non barré (3) et marquez-le premier
• Étape 4 : Barrez tous les multiples de ce nombre premier
• Étape 5 : Répétez jusqu’à √n
• Résultat : Tous les nombres non barrés sont premiers

Somme des nombres premiers

Somme des n premiers nombres premiers :

• 10 premiers : 2+3+5+7+11+13+17+19+23+29 = 129
• 100 premiers : somme = 24 133
• 1 000 premiers : somme = 3 682 913

Somme des nombres premiers jusqu’à n :

• Jusqu’à 10 : 2+3+5+7 = 17
• Jusqu’à 100 : somme = 1 060
• Jusqu’à 1 000 : somme = 76 127

Théorème des nombres premiers

Le nombre de nombres premiers inférieurs à n est approximativement n/ln(n) :

• Jusqu’à 100 : ~25 (réel : 25)
• Jusqu’à 1 000 : ~145 (réel : 168)
• Jusqu’à 10 000 : ~1 086 (réel : 1 229)
• Jusqu’à 100 000 : ~8 686 (réel : 9 592)

Types de nombres premiers

Nombres premiers jumeaux : nombres premiers qui diffèrent de 2

• (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43)...

Nombres premiers de Mersenne : de la forme 2ᵖ - 1 où p est premier

• 2² - 1 = 3
• 2³ - 1 = 7
• 2⁵ - 1 = 31
• 2⁷ - 1 = 127
• Le plus grand nombre premier connu est de type Mersenne (24,8 millions de chiffres !)

Nombres premiers de Sophie Germain : premier p tel que 2p+1 soit aussi premier

• 2 (2×2+1 = 5), 3 (2×3+1 = 7), 5 (2×5+1 = 11), 11, 23, 29...

Nombres premiers de Fermat : de la forme 2^(2ⁿ) + 1

• F₀ = 3, F₁ = 5, F₂ = 17, F₃ = 257, F₄ = 65 537
• On ne connaît que 5 nombres premiers de Fermat

Applications des nombres premiers

Cryptographie (RSA) :

• Basée sur la difficulté de factoriser de grands nombres
• Utilise deux grands nombres premiers (centaines de chiffres)
• Sécurise la banque en ligne, les e-mails et les sites web

Tables de hachage :

• Des tailles premières réduisent les collisions
• Utilisées dans les bases de données et le cache

Génération de nombres aléatoires :

• Les nombres premiers améliorent les séquences pseudo-aléatoires
• Utilisés dans les simulations et les jeux

Faits intéressants

• Infinité : démontrée par Euclide ~300 av. J.-C. – les nombres premiers ne s’arrêtent jamais
• Écarts : peuvent être arbitrairement grands
• Conjecture de Goldbach : tout nombre pair > 2 est somme de deux nombres premiers (non prouvée !)
• Hypothèse de Riemann : prix d’un million de dollars pour une preuve liée à la répartition
• Écarts entre premiers : la différence entre deux premiers consécutifs augmente
• Probabilité : un nombre aléatoire n a ~1/ln(n) chance d’être premier

Records

• Plus grand premier connu : 2^82,589,933 - 1 (découvert en 2018, 24 862 048 chiffres)
• Plus grands nombres premiers jumeaux : 2 996 863 034 895 × 2^1 290 000 ± 1
• Calcul : GIMPS (Great Internet Mersenne Prime Search), projet distribué

Idées reçues

• 1 n’est PAS premier : selon la définition moderne (exactement 2 diviseurs)
• Tous les impairs ne sont pas premiers : 9, 15, 21, 25... sont composés
• Formule pour tous les premiers : il n’existe pas de formule simple
• Motif dans les premiers : pas de motif prévisible (ils semblent aléatoires)

💡 Conseil : Pour vérifier si un grand nombre est premier, il suffit de tester la divisibilité jusqu’à sa racine carrée ! Par exemple, pour 997, testez jusqu’à √997 ≈ 31,6 : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31. Si aucun ne divise 997 exactement, il est premier ! De plus, sauf 2 et 3, tous les premiers sont de la forme 6k±1, ce qui peut accélérer la recherche.