La manera más eficiente de encontrar todos los números primos pequeños (digamos menores a 10,000,000) es usando la Criba de Eratóstenes:
Hacer una lista de todos los números enteros menores o iguales a n (y mayores que uno). Tachar los múltiplos de todos los números primos menores o iguales a la raíz de n, los número que queden sin tachar son los primos. Por ejemplo, para encontrar todos los primos menores que o iguales a 30, primero hacemos una lista con los números desde 2 hasta 30.
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 El primer número no tachado es primo, en este caso 2, lo mantenemos (indicaremos que es primo mostrándolo en color azul y en un recuadro) y tachamos a sus múltiplos (indicaremos que fueron tachados mostrándolos en color rojo y subrayados), así que todos los número en rojo no son primos.
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 El siguiente número restante (todavía en negro) es 3. Tachamos a todos sus múltiplos. Sabemos que todos sus múltiplos menores que 9 (i.e. 6) han sido tachados, así que podemos iniciar a tachar a partir de 32 = 9.
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 Ahora el primer número restante (todavía en negro) es 5. Tachamos todos sus múltiplos (todos sus múltiplos menores a 52 = 25 han sido tachados).
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 El siguiente número restante es 7, el cual es mayor que la raíz cuadrada de 30, así que no quedan múltiplos por tachar y la criba está completa. Todos los números primos restantes son primos: {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}.
Verificar si un número es primo Para verificar si un número es o no primo nos vamos a apoyar en la criba de Eratóstenes.
Para determinarlo hacemos lo siguiente: a) si el número es menor que MAX verificamos si es primo o no usando el arreglo primo (es primo si primo[num] es igual a cero). b) si el numero es mayor igual que MAX, usamos el arreglo primos y vamos probando si el numero es divisible entre alguno de los primos calculados, si es así entonces el numero no es primo, en caso contrario es primo.
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997
La manera más eficiente de encontrar todos los números primos pequeños (digamos menores a 10,000,000) es usando la Criba de Eratóstenes:
Hacer una lista de todos los números enteros menores o iguales a n (y mayores que uno). Tachar los múltiplos de todos los números primos menores o iguales a la raíz de n, los número que queden sin tachar son los primos.
Por ejemplo, para encontrar todos los primos menores que o iguales a 30, primero hacemos una lista con los números desde 2 hasta 30.
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
El primer número no tachado es primo, en este caso 2, lo mantenemos (indicaremos que es primo mostrándolo en color azul y en un recuadro) y tachamos a sus múltiplos (indicaremos que fueron tachados mostrándolos en color rojo y subrayados), así que todos los número en rojo no son primos.
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
El siguiente número restante (todavía en negro) es 3. Tachamos a todos sus múltiplos. Sabemos que todos sus múltiplos menores que 9 (i.e. 6) han sido tachados, así que podemos iniciar a tachar a partir de 32 = 9.
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
Ahora el primer número restante (todavía en negro) es 5. Tachamos todos sus múltiplos (todos sus múltiplos menores a 52 = 25 han sido tachados).
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
El siguiente número restante es 7, el cual es mayor que la raíz cuadrada de 30, así que no quedan múltiplos por tachar y la criba está completa. Todos los números primos restantes son primos: {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}.
Verificar si un número es primo
Para verificar si un número es o no primo nos vamos a apoyar en la criba de Eratóstenes.
Para determinarlo hacemos lo siguiente:
a) si el número es menor que MAX verificamos si es primo o no usando el arreglo primo (es primo si primo[num] es igual a cero).
b) si el numero es mayor igual que MAX, usamos el arreglo primos y vamos probando si el numero es divisible entre alguno de los primos calculados, si es así entonces el numero no es primo, en caso contrario es primo.
Espero Que te Sirva Saludos ^^♥