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.
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 (= 2
53)
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.
Max | 1000 | 10000 | 100000 | 1000000 | 10000000 | 100000000 | 1000000000 |
n | 168 | 1229 | 9592 | 78498 | 664579 | 5761455 | 50847534 | memory |
0. Essais de division |
---|
Div0 | 2 | 63 | 3365 | - | - | - | - | - |
Div1 | 1 | 42 | 1770 | 145128 | - | - | - | - |
Div2 | 0 | 2 | 35 | 309 | 7579 | - | - | - |
Div3 | 0 | 2 | 31 | 305 | 6799 | - | - | - |
Div4 | 0 | 1 | 30 | 296 | 6564 | - | - | - |
1. Essais de division avec liste |
---|
List0 | 0 | 1 | 26 | 323 | 7301 | - | - | int[n] |
List1 | 0 | 1 | 19 | 172 | 2557 | - | - | int[n] |
2. Crible d'Ératosthène |
---|
Sieve0 | 0 | 1 | 11 | 79 | 659 | 7104 | - | bool[Max] |
Sieve1 | 0 | 1 | 9 | 63 | 466 | 5003 | - | bool[Max] |
Sieve2 | 0 | 1 | 11 | 20 | 142 | 1495 | - | bool[Max/2] |
Sieve3 | 0 | 0 | 9 | 23 | 138 | 1455 | - | bool[Max/2] |
SieveA | 0 | 0 | 0 | 0 | 31 | 592 | 7237 | bool[Max/2] |
SieveB | 0 | 0 | 0 | 0 | 31 | 592 | 7223 | bool[Max/2] |
SieveC | 0 | 0 | 0 | 0 | 16 | 312 | 4696 | bit[Max/2] |
EratoA | 0 | 0 | 0 | 0 | 94 | 1326 | 16411 | bool[Max] |
EratoB | 0 | 0 | 0 | 0 | 94 | 1248 | 15085 | bool[Max] |
EratoC | 0 | 0 | 0 | 0 | 78 | 1232 | 15071 | bool[Max] |
EratoD | 0 | 0 | 0 | 0 | 31 | 421 | 4680 | bool[Max] |
EratoE | 0 | 0 | 0 | 0 | 31 | 437 | 4627 | bool[Max] |
EratoOdd | 0 | 0 | 0 | 15 | 265 | 2808 | bool[Max/2] |
3. Crible d'Atkin (Biz. inédit ?) |
---|
Atkin0 | 0 | 0 | 4 | 44 | 399 | 4847 | - | bool[Max] |
Atkin1 | 0 | 1 | 4 | 42 | 478 | 4777 | - | bool[Max] |
Atkin2 | 0 | 0 | 4 | 42 | 373 | 4029 | - | bool[Max] |
Atkin3-Biz | 0 | 2 | 31 | 297 | 2905 | - | bool[Max] |
Atkin4-Biz | 0 | 1 | 19 | 270 | 2799 | - | bool[Max] |
Atkin5-Biz | 0 | 4 | 20 | 273 | 2786 | - | bool[Max] |
AtkinA-Biz. | 0 | 0 | 0 | 109 | 1529 | 17628 | bool[Max] |
AtkinB-Biz. | 0 | 0 | 0 | 46 | 1154 | 16318 | bit[Max] |
AtkinC-Biz. | 0 | 0 | 0 | 31 | 530 | 8088 | bool[Max] |
AtkinD-Biz. | 0 | 0 | 0 | 0 | 359 | 5397 | bit[Max] |
AtkinE-Biz. | 0 | 0 | 0 | 0 | 422 | 6302 | bit[Max] |
4. Crible avec cycle additif |
---|
CycleA | 0 | 0 | 2 | 35 | 629 | - | - | bool[Max/2] |
CycleB | 0 | 0 | 1 | 9 | 100 | 1206 | - | bool[Max/2] |
CycleC | 0 | 0 | 1 | 4 | 111 | 1414 | - | bool[Max/2] |
Cycle23 | 0 | 1 | 4 | 83 | 1152 | - | bool[Max/2] |
Cycle235 | 0 | 1 | 15 | 90 | 1001 | - | bool[Max/3] |
Cycle2357 | 0 | 1 | 7 | 80 | 857 | - | bool[Max/4.375] |
5. Crible des multiplications (inédit ?) |
---|
Mult0 | 12 | 456 | 140532 | - | - | - | - | bool[Max] |
Mult1 | 0 | 0 | 4 | 48 | 787 | 10139 | - | bool[Max] |
Mult2 | 0 | 0 | 5 | 36 | 776 | 10091 | - | bool[Max] |
Mult3 | 0 | 0 | 3 | 25 | 226 | 2616 | - | bool[Max] |
Mult4 | 0 | 0 | 2 | 17 | 111 | 1307 | - | bool[Max/2] |
Mult5-Sundaram | 3 | 51 | 491 | 5356 | - | bool[Max/2] |
Mult6-Sundaram-Opt | 1 | 19 | 119 | 1363 | - | bool[Max/2] |
Mult7 | 0 | 0 | 1 | 8 | 77 | 850 | - | bool[Max/3] |
MultA | 0 | 0 | 0 | 0 | 15 | 319 | 4836 | bool[Max/3] |
MultB | 0 | 0 | 0 | 0 | 15 | 188 | 3650 | bit[Max/3] |
6. Crible segmenté |
---|
SegmA | 00 | 0 | 0 | 0 | 16 | 140 | 1688 | bool[32768] |
SegmC | 00 | 0 | 0 | 1 | 8 | 96 | 1182 | bool[32768] |
SegmD | 00 | 0 | 0 | 0 | 8 | 87 | 1005 | bool[32768] |
7. Crible avare |
---|
AvareA | 00 | 0 | 0 | 5 | 62 | 639 | - | byte[Max] |
AvareOdd | 0 | 0 | 3 | 36 | 417 | - | 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).