Criba de Eratóstenes

Algoritmo

De acuerdo con la Wikipedia la Criba de Eratóstenes es un algoritmo que permite hallar todos los números primos menores que un número natural n, mediante el siguiente proceso:

1. Listar los valores de 2 a n
2. Tomar el primer número no tachado o marcado como número primo y se marca como primo
3. Tachar los múltiplos del número que se acaban de marcar como primo
4. Si el cuadrado del número que se indicó como primo es igual o menor que n, se vuelve al paso 2. De lo contrario, termina el proceso.

Gráficamente, el proceso se realizaría de la siguiente forma:

Código para R

primos = function(x){
  numeros = 2:x
  d = 1
  while(numeros[d]^2 <= x){
    for(n in numeros){
      if(numeros[d] != n){
        if(n%%numeros[d]==0){
          numeros = numeros[-which(numeros==n)]
        }
      }
    }
    d=d+1
  }
numeros
}

primos(200)

##  [1]   2   3   5   7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67
## [20]  71  73  79  83  89  97 101 103 107 109 113 127 131 137 139 149 151 157 163
## [39] 167 173 179 181 191 193 197 199

Código para Python

import numpy as np

def primos(x):
    numeros = list(range(2,x+1))
    d=0
    while numeros[d]**2 <= x:
        for n in numeros:
            if n != numeros[d]:
              if n % numeros[d] == 0:
                numeros.remove(n)
        d += 1
    return numeros

primos(200)

## [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]

\[\ \]

Contacto: Fiverr Twitter edison.lmg@gmail.com

\[\ \]