Nombres premiers

    Version: février 2017.                  par William VOIROL, Switzerland    [Site Web]

Définition:

Un nombre entier (>1) est dit premier s'il n'admet aucun diviseur autre que 1 et lui-même.

Mon but est de familiariser le lecteur avec quelques codes en HTML/Javascript et C/C++ concernant les nombres premiers.

GroupeTitreDateCodes-SourcesZip
0-DivEssais de divisionJuin 2013 0-Div Div.zip
1-ListEssais de division avec listeJuin 2013 1-List List.zip
2-SieveCrible d'ÉratosthèneJuillet 2013 2-Sieve Sieve.zip
2-SieveCrible d'ÉratosthèneSeptembre 2013 2-Sieve Sieve.zip
2-SieveÉratosthène classiqueMars 2014 2-Erato Erato.zip
3-AtkinCrible d'AtkinSeptembre 2013 3-Atkin Atkin.zip
3-AtkinCrible d'Atkin bizarreFévrier 2014 3-Atkin-Biz Atkin-Biz.zip
3-AtkinCrible d'Atkin bizarreFévrier 2014 3-Atkin-Biz Atkin.zip
4-CycleCrible avec cycle additifMars 2014 4-Cycle Cycle.zip
4-CycleCrible avec cycle additif BisMars 2014 4-Cycle-Bis Cycle-Bis.zip
5-MultCrible des multiplicationsOctobre 2013 5-Mult Mult.zip
5-MultCrible des multiplicationsOctobre 2013 5-Mult Mult-C.zip
6-SegmCrible segmentéJuillet 2016 6-Segm Segm-C.zip
7-AvareCrible avareAoût 2016 7-Avare AvareA.zip
8-FactorDécomposition en facteurs premiersen préparation 8-Factor Factor.zip
9-PrimTest de primalitéen préparation 9-Prim Prim.zip

Chaque groupe est (ou sera) composé d'un code initial interprétant l'algorithme étudié, suivi d'améliorations "classiques" ou personnelles.
Tous les codes présentés sont d'édition propre (pas de copier-coller) et ont été faites avec le souci de simplification et d'optimisation.

Remarques éventuelles:  de préférence sur CodeS-SourceS    sinon:   email@william-voirol.ch    (pas de pub ! SVP)

Liste de nombres premiers:   CycleOut.    Essayez avec Max = 10000000 !

Décomposition en facteurs premiers:   Factors.    Avec 2 ≤ n < 9007199254740992 (= 253)

Plus grand commun diviseur de plusieurs nombres:   PGCD.

Temps d'exécution en ms:

Les mesures dépendent de l'ordinateur, du navigateur et de leur charge.
Je donne chaque fois le meilleur résultat d'une série de tests sur un ordinateur i5 3.2 GHz.
0000
Max1000100001000001000000100000001000000001000000000
n1681229959278498664579576145550847534memory
0. Essais de division
Div02633365-----
Div11421770145128----
Div202353097579---
Div302313056799---
Div401302966564---
1. Essais de division avec liste
List001263237301--int[n]
List101191722557--int[n]
2. Crible d'Ératosthène
Sieve00111796597104-bool[Max]
Sieve1019634665003-bool[Max]
Sieve20111201421495-bool[Max/2]
Sieve3009231381455-bool[Max/2]
SieveA0000315927237bool[Max/2]
SieveB0000315927223bool[Max/2]
SieveC0000163124696bit[Max/2]
EratoA000094132616411bool[Max]
EratoB000094124815085bool[Max]
EratoC000078123215071bool[Max]
EratoD0000314214680bool[Max]
EratoE0000314374627bool[Max]
EratoOdd000152652808bool[Max/2]
3. Crible d'Atkin (Biz. inédit ?)
Atkin0004443994847-bool[Max]
Atkin1014424784777-bool[Max]
Atkin2004423734029-bool[Max]
Atkin3-Biz02312972905-bool[Max]
Atkin4-Biz01192702799-bool[Max]
Atkin5-Biz04202732786-bool[Max]
AtkinA-Biz.000109152917628bool[Max]
AtkinB-Biz.00046115416318bit[Max]
AtkinC-Biz.000315308088bool[Max]
AtkinD-Biz.00003595397bit[Max]
AtkinE-Biz.00004226302bit[Max]
4. Crible avec cycle additif
CycleA00235629--bool[Max/2]
CycleB00191001206-bool[Max/2]
CycleC00141111414-bool[Max/2]
Cycle23014831152-bool[Max/2]
Cycle2350115901001-bool[Max/3]
Cycle235701780857-bool[Max/4.375]
5. Crible des multiplications (inédit ?)
Mult012456140532----bool[Max]
Mult10044878710139-bool[Max]
Mult20053677610091-bool[Max]
Mult3003252262616-bool[Max]
Mult4002171111307-bool[Max/2]
Mult5-Sundaram3514915356-bool[Max/2]
Mult6-Sundaram-Opt1191191363-bool[Max/2]
Mult7001877850-bool[Max/3]
MultA0000153194836bool[Max/3]
MultB0000151883650bit[Max/3]
6. Crible segmenté
SegmA0000161401688bool[32768]
SegmC00018961182bool[32768]
SegmD00008871005bool[32768]
7. Crible avare
AvareA000562639-byte[Max]
AvareOdd00336417-byte[Max/2]
8. Décomposition en facteurs premiers
Factor0
9. Test de primalité
Prim0

Juxtaposition de quelques codes qui utilisent la notion de crible:

Test avec Max = 4'294'709'602 (=> 203'268'793 nombres premiers).
annéetemps d'exéc.mémoireCodeS-SourceS
200353.461 sbit[Max/2] 1 000 000 de nombres premiers en 0.062 secondes
201163.773 sbit[Max/2] Crible d'eratosthène optimisé
201323.167 sbit[Max/2] Nombres premiers: crible d'Eratosthène
201317.659 sbit[Max/3] Nombres premiers: crible des multiplications
201414.925 sbool[Max/2] Le crible d'Eratosthène classique
20168.906 sbool[32768] Nombres premiers: Crible segmenté (A)
20166.429 sbool[32768] Nombres premiers: Crible segmenté (C)
20174.93 sbool[32768] Nombres premiers: Crible segmenté (D)
InterNet
2013 ?10.862 schar[32768] Simple segmented sieve, primesieve, Kim Wallisch
20130.65 sbit[?] Optimized segmented sieve, primesieve, Kim Wallisch