Búsqueda

Visitas: 36776

Numeros Primos

Definición: Un número entero mayor que uno es llamado un número primo si sus único divisores positivos son uno y él mismo.

Los primeros 100 números primos son:

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

Hay 168 números primos menores a 1000:

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 773 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

Criba de Eratóstenes

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 tachamos a sus múltiplos (indicaremos que fueron tachados mostrándolos subrayados), así que todos los número en negritas y subrayados 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 sin marcar) 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 sin marcar) 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}.

    Criba(n)
    {
      a[1] = 0;
      for (i = 2; i <= n; i++)
        a[i] := 1
      for (p = 2; p * p <= n; p++)
        if (a[p] == 1)
          for (j = p * p; p * p <= n; j += p)
            a[j] = 0
      return (a);
    }
 

La criba de Eratóstenes es un algoritmo que permite hallar todos los números primos menores que un número natural dado N. Se forma una tabla con todos los números naturales comprendidos entre 2 y N y se van tachando los números que no son primos de la siguente manera: cuando se encuentra un entero que no ha sido tachado, ese número es declarado primo, y se procede a tachar todos sus múltiplos. El proceso termina cuando el cuadrado del mayor numero confirmado como primo es mayor que N.

#include <bitset>
#include <vector>

#define MAXPRIME 10000  // debe ser igual a la raiz cuadrada del máximo número que vamos a manejar
bitset <MAXPRIME> criba;
vector <int> primos;

void llena_criba()
{
  criba.set();   // marcamos a los N números naturales como primos
  for (int i=2; i<MAXPRIME; i++)
    if (criba.test( i ))   // primo, dado que no ha sido tachado
    {
      primos.push_back( i );
      for (int j=2*i; j<MAXPRIME; j+=i)
        criba.reset( j )// tachamos a los múltiplos del número

    }
}
 

En el código principal se debe llamar a la función llena_criba, tomar en cuenta que la llamada a dicha función solo debe hacerse una vez durante la ejecución del programa.

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 asi entonces el numero no es primo, en caso contrario es primo.

// verificamos si un numero es primo usando el algoritmo descrito
// previamente
bool es_primo(int n)
{
  int i=0;

  if (n < MAX) return !primo[n];
  while(primos[i]*primos[i] <= n)
    if (n % primos[i] == 0) return false;
    else i++;
  return true;
}
 

Problemas relacionados en la UVA

10140 - Prime Distance
10394 - Twin Primes