danielhagnoul

Calcul des nombres premiers (100000 en 0,180s)

Noter ce billet

par

, 20/07/2017 à 19h29 (1869 Affichages)

J'ai rédigé ce billet après avoir lu [Python3] Nombres premiers : trouver les énièmes premiers de Nothus.

J'ai utilisé la même méthode de calcul : Number.isInteger( n / premier ).

La fonction kNbPremiers( X = 25 ) retourne un Array contenant X nombres premiers en partant de l'Array [ 2, 3 ].

Le calcul des 100000 premiers nombres premiers prend :

plus ou moins 0,180s avec Chrome 60b ;
plus ou moins 0,700s avec Fiferox 55b ;
plus ou moins 22,800s avec Edge 15.

La fonction kNbPremiersDuAu( premiers = [ 2, 3 ], a = 0, b = premiers.length - 1 ) retourne un Array de nombres premiers allant, par défaut, du premier au dernier.

La fonction kNbPremiersComprisEntreAetB( premiers = [ 2, 3 ], a = 0, b = 4 ) retourne un Array de nombres premiers compris, par défaut, entre 0 et 4.

Les fonctions

Code JavaScript :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
const	
	kNbPremiers = ( X = 25 ) => {
		// Array contenant X nombres premiers.
 
		let
			premiers = [ 2, 3 ],
			limite = 0,
			boolPremier = false,
			maxPremier = 0,
			range = [];
 
		while ( premiers.length < X ){
			limite = 0;
			boolPremier = false;
			maxPremier = premiers[ premiers.length - 1 ];
			range = [];
 
			for ( let i = maxPremier + 1; i < maxPremier * 2 + 1; i++ ){
				range.push( i );
			}
 
			for ( const n of range ){
				limite = Math.sqrt( n );
 
				for ( const premier of premiers ){								
					if ( premier > limite ) break;
 
					if ( Number.isInteger( n / premier ) ){
						boolPremier = false;
						break;
					} else {
						boolPremier = true;
					}
				}
 
				if ( boolPremier ){
					premiers.push( n );
					boolPremier = false;
 
					if ( premiers.length === X ){
						break;
					}
				}
			}
		}
 
		return premiers;
	},
	kNbPremiersDuAu = ( premiers = [ 2, 3 ], a = 0, b = premiers.length - 1 ) => {
		// Array de nombres premiers allant, par défaut, du premier au dernier
 
		let
			result = [];
 
		for ( let i = ( ( a < premiers.length - 1 ) ? a : ( premiers.length - 1 ) ); i < ( ( b + 1 < premiers.length ) ? ( b + 1 ) : premiers.length ); i++ ){
			result.push( premiers[ i ] );
		}
 
		return result;
	},
	kNbPremiersComprisEntreAetB= ( premiers = [ 2, 3 ], a = 0, b = 4 ) => {
		// Array de nombres premiers compris, par défaut, entre 0 et 4
 
		let
			result = [];
 
		const 
			debut = ( a < premiers[ premiers.length - 1 ] && a > -1 ) ? a : 0,
			fin = ( b < premiers[ premiers.length - 1 ] ) ? b : premiers[ premiers.length - 1 ];
 
		for ( const premier of premiers ){
			if ( premier > debut ){
				if ( premier < fin ){
					result.push( premier );
				} else {
					break;
				}
			}
		}
 
		return result;
	};

Exemple

Code JavaScript :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
<!DOCTYPE html>
<html lang="fr" dir="ltr">
<head>
	<!-- cache-control avec max-age=60 pour le développement uniquement -->
  <meta http-equiv="cache-control" content="public, max-age=60">
  <meta charset="utf-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0, shrink-to-fit=no">
  <meta name="author" content="Daniel Hagnoul">
  <title>test</title>
  <style>
    * {
      box-sizing: border-box;
    }		
 
		/* CSS du test */
 
 
		/* Fin CSS du test */
 
  </style>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/moment.js/2.18.1/moment.min.js"></script>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/moment.js/2.18.1/locale/fr.js"></script>
  <script src="http://danielhagnoul.developpez.com/lib/dvjh/dvjhUtilities-1.3.3.js"></script>
  <script>
    'use strict';
 
    document.addEventListener( "DOMContentLoaded", ev => {
			moment.locale( "fr" );
			klog( `DOM ready   : ${ new kDvjhDate() }` );
 
      // code du test
 
 
			// fin code du test
 
    }, false );
 
    window.addEventListener( "load", ev => { 
			klog( `Window load : ${ new kDvjhDate() }` );
 
      // code du test
 
			const	
				kNbPremiers = ( X = 25 ) => {
					// Array contenant X nombres premiers.
 
					let
						premiers = [ 2, 3 ],
						limite = 0,
						boolPremier = false,
						maxPremier = 0,
						range = [];
 
					while ( premiers.length < X ){
						limite = 0;
						boolPremier = false;
						maxPremier = premiers[ premiers.length - 1 ];
						range = [];
 
						for ( let i = maxPremier + 1; i < maxPremier * 2 + 1; i++ ){
							range.push( i );
						}
 
						for ( const n of range ){
							limite = Math.sqrt( n );
 
							for ( const premier of premiers ){								
								if ( premier > limite ) break;
 
								if ( Number.isInteger( n / premier ) ){
									boolPremier = false;
									break;
								} else {
									boolPremier = true;
								}
							}
 
							if ( boolPremier ){
								premiers.push( n );
								boolPremier = false;
 
								if ( premiers.length === X ){
									break;
								}
							}
						}
					}
 
					return premiers;
				},
				kNbPremiersDuAu = ( premiers = [ 2, 3 ], a = 0, b = premiers.length - 1 ) => {
					// Array de nombres premiers allant, par défaut, du premier au dernier
 
					let
						result = [];
 
					for ( let i = ( ( a < premiers.length - 1 ) ? a : ( premiers.length - 1 ) ); i < ( ( b + 1 < premiers.length ) ? ( b + 1 ) : premiers.length ); i++ ){
						result.push( premiers[ i ] );
					}
 
					return result;
				},
				kNbPremiersComprisEntreAetB= ( premiers = [ 2, 3 ], a = 0, b = 4 ) => {
					// Array de nombres premiers compris, par défaut, entre 0 et 4
 
					let
						result = [];
 
					const 
						debut = ( a < premiers[ premiers.length - 1 ] && a > -1 ) ? a : 0,
						fin = ( b < premiers[ premiers.length - 1 ] ) ? b : premiers[ premiers.length - 1 ];
 
					for ( const premier of premiers ){
						if ( premier > debut ){
							if ( premier < fin ){
								result.push( premier );
							} else {
								break;
							}
						}
					}
 
					return result;
				};
 
			const premiers = kNbPremiers( 100000 );
 
			klog( `Calcul terminé : ${ new kDvjhDate() }` );  // plus ou moins 0.180s pour 100000 nombres premiers sur Chrome 60b
 
			// les nombres premiers du premier (0) au 25e
			klog( ( kNbPremiersDuAu( premiers, 0, 25 ) ).join( ", " ) );
 
			// les nombres premiers du 100e au 1000e
			klog( ( kNbPremiersDuAu( premiers, 100, 1000 ) ).join( ", " ) );
 
			// les nombres premiers entre 100 et 1000
			klog( ( kNbPremiersComprisEntreAetB( premiers, 100, 1000 ) ).join( ", " ) );
 
			// debug : https://fr.wikipedia.org/wiki/Liste_de_nombres_premiers
 
			// fin code du test
 
      kIDUnique();
    }, false );
  </script>
</head>
<body>
	<main>
 
	</main>
</body>
</html>