Liste des Nombres Premiers
Générez tous les nombres premiers jusqu'à n avec le crible d'Ératosthène.
Maximum : 10 000
Le crible d'Ératosthène
Le crible d'Ératosthène est un algorithme antique (IIIe siècle av. J.-C.) permettant de trouver tous les nombres premiers jusqu'à une limite donnée. Son principe : on commence avec tous les entiers de 2 à n, puis on élimine successivement les multiples de chaque nombre premier rencontré.
Algorithme
1. Créer une liste de 2 à n, tous "premier"
2. Pour p = 2 : marquer tous les multiples de p (4, 6, 8...) comme "non premier"
3. Passer au prochain nombre non marqué (3), répéter
4. S'arrêter quand p > √n
5. Tous les nombres restants non marqués sont premiers
Théorème des nombres premiers
Le nombre de nombres premiers ≤ n, noté π(n), est approximativement n / ln(n). Par exemple, π(1000) ≈ 168, π(10000) ≈ 1229.
Faits remarquables
- 2 est le seul nombre premier pair
- Tous les premiers > 3 sont de la forme 6k ± 1
- Les jumeaux premiers sont des paires (p, p+2) toutes deux premières : (11,13), (17,19), (41,43)...
- Le plus grand premier connu (2025) a plus de 41 millions de chiffres (2^136279841−1)