Uanl

La criba de Eratóstenes
Pero, ¿cómo se generan esos números primos?
es un algoritmo que permite hallar todos los números primos menores que un número natural dado N. Se forma una tabla con todoslos números naturales comprendidos entre 2 y N y se van tachando los números que no son primos de la siguiente manera: cuando se encuentra un número entero que no ha sido tachado, ese número esdeclarado primo, y se procede a tachar todos sus múltiplos. El proceso termina cuando el cuadrado del mayor número confirmado como primo es mayor que N.
Por ejemplo: los múltiplos de 2 que se van a eliminarde la Tabla, mediante esta Criba, son el 4, 6, 8, 10, etc., que son los múltiplos de 2 mayores o iguales que 4. Procediendo así, se muestra a continuación la Criba de Eratóstenes que se obtiene paralos primeros 1000 números naturales, los primeros 168 nùmeros primos.

CRIBA DE ERATÓSTENES PARA LOS PRIMEROS 1000 NÚMEROS NATURALES | | |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 4 | |
11 |12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 4 | |
21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 2 | |
31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 2 | |
41 | 42 | 43 | 44 | 45 | 46| 47 | 48 | 49 | 50 | 3 | |
51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 2 | |
61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 2 | |
71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 | 3| |
81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 2 | |
91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 | 1 | 25 |
101 | 102 | 103 | 104 | 105 | 106 | 107 | 108 | 109 | 110 | 4 | |111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 1 | |
121 | 122 | 123 | 124 | 125 | 126 | 127 | 128 | 129 | 130 | 1 | |
131 | 132 | 133 | 134 | 135 | 136 | 137 | 138 | 139 | 140 | 3 ||
141 | 142 | 143 | 144 | 145 | 146 | 147 | 148 | 149 | 150 | 1 | |
151 | 152 | 153 | 154 | 155 | 156 | 157 | 158 | 159 | 160 | 2 | |
161 | 162 | 163 | 164 | 165 | 166 | 167 | 168 | 169 |...