Générateur nombres premiers test primalité factorisation entiers

Ce générateur nombres premiers utilise crible Ératosthène algorithme efficace liste nombres premiers jusqu'à N complexité O(n log log n) élimination multiples successifs optimisé grandes valeurs. Test primalité algorithme division simple exact complexité O(√n) test Fermat probabiliste petit théorème Fermat a^(p-1) ≡ 1 (mod p) Miller-Rabin probabiliste très fiable décomposition n-1 = 2^r × d témoin aléatoires confiance élevée. Factorisation entiers décomposition produit facteurs premiers algorithme division successive complexité dépend taille facteurs applications cryptographie RSA sécurité clés théorie nombres propriétés arithmétiques.

Questions fréquentes (FAQ)

Qu'est-ce qu'un nombre premier ?

Nombre entier naturel n ≥ 2 divisible uniquement par 1 et lui-même. Exemples : 2, 3, 5, 7, 11, 13... Le nombre 2 est le seul premier pair. Infinité démontrée par Euclide (300 av. J.-C.).

Comment fonctionne le crible d'Ératosthène ?

Algorithme antique (vers 240 av. J.-C.) : (1) Liste 2 à N, (2) Marquer 2 premier, barrer multiples (4,6,8...), (3) Prochain non barré (3) premier, barrer multiples (6,9,12...), (4) Répéter jusqu'à √N. Très efficace grandes listes.

Qu'est-ce que la factorisation en nombres premiers ?

Théorème fondamental arithmétique : tout entier n > 1 s'écrit de manière unique comme produit de nombres premiers. Ex: 360 = 2³ × 3² × 5. Applications : cryptographie RSA (difficulté factoriser grands nombres), PGCD, PPCM.