Criba de Eratóstenes

De Wikipedia, la enciclopedia libre

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 siguiente manera: cuando se encuentra un número 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 número confirmado como primo es mayor que N.

[editar] Proceso de criba

Determinemos, el proceso, la lista de los números primos menores de 20.

Primer paso: pongamos los números naturales comprendidos entre 2 y 20.

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

2. Segundo paso: Marcamos el primer número ,no rayado ni marcado, como número primo.

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

3. Tercer paso: Tachamos todos los múltiplos del número que acabamos de marcar como primo.

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

4. Cuarto paso: Si el cuadrado del primer número que no ha sido rayado ni marcado es inferior a 20, entonces repetimos el segundo paso. Si no, el algoritmo termina, y todos los enteros no tachados son declarados primos.

Como 3² = 9 < 20, volvemos al segundo paso:

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

En el cuarto paso, el primer número que no ha sido tachado ni marcado es 5. Como su cuadrado es mayor que 20, el algoritmo termina y consideraremos primos todos los números que no han sido tachados.

Resultado: Los números primos comprendidos entre 2 y 20 son: 2, 3, 5, 7, 11, 13, 17, 19.

[editar] Pseudocódigo

Algoritmo Criba de Eratóstenes (Complejidad $\mathcal{O}(n~\log^2 n~\log\log n)$ )
Entrada: Un número natural $n$ Salida: El conjunto de números primos anteriores a $n$ (incluyendo $n$ ) Escriba todos los números naturales desde $2$ hasta $n$ Para $i$ desde $2$ hasta $\lfloor \sqrt n\rfloor$ haga lo siguiente: Si $i$ no ha sido marcado entonces: Para $j$ desde $i$ hasta $n\div i$ haga lo siguiente: Ponga una marca en $i\times j$ El resultado es: Todos los números sin marca

Acerca de la notación:

$\lfloor x\rfloor$ es la función parte entera de $x$
$a\div b$ es el cociente de dividir $a$ entre $b$

Para su implementación en una computadora, normalmente se maneja un vector de tipo lógico con $n$ elementos. De esta manera, la posición $i$ contiene el valor Verdadero como representación de que $i$ ha sido marcado y Falso en otro caso.

[editar] Implementacion

En lenguaje Python

 
#Criba de Erastostenes por Calvo
from math import sqrt,floor
 
n=input()
d={}
p=2,
 
for i in range(2,floor(sqrt(n))+1):
    if i not in d.keys():
        for j in range(i,n/i+1): d[i*j]=1
 
for i in range(n,1,-1):
    if i not in d.keys(): print i

En Lenguaje de programación Ada

procedure Eratosthenes(Result : out Integer) is
   size : constant := 8190;
   k, prime : Natural;
   count : Integer;
 
   type Ftype is array (0 .. Size) of Boolean;
   Flags : Ftype;
 
begin
   for Iter in 1 .. 10 loop
      count := 0;
 
      for i in 0 .. size loop
         Flags (i) := True;
      end loop;
 
      for i in 0 .. size loop
         if Flags (i) then
            prime := i + i + 3;
            k := i + prime;
            while k <= size loop
               Flags (k) := False;
               k := k + prime;
            end loop;
            count := count + 1;
         end if;
      end loop;
   end loop;
 
   Result := count;
end Eratosthenes;

En lenguaje Basic

defint a-z
size=50
dim flags(50)
for i=2 to size
  flags(i)=-1
next
for i=2 to sqr(size)
  if flags(i) then
    for k=i*i to size step i
      flags(k)=0
    next
  end if
next
 
for i=0 to size
  if flags(i) then print i;
next
print

En lenguaje Bash

#!/bin/bash
 
UPPER_LIMIT=$1                  
let SPLIT=UPPER_LIMIT/2         
 
Primes=( '' $(seq $UPPER_LIMIT) )
 
i=1
until (( ( i += 1 ) > SPLIT ))  
do
  if [[ -n $Primes[i] ]]
  then
    t=$i
    until (( ( t += i ) > UPPER_LIMIT ))
    do
      Primes[t]=
    done
  fi  
done  
echo ${Primes[*]}
 
exit 0

En Lenguaje de programación C

/* Sieve Of Erathosthenes by Denis Sureau */
#include <stdlib.h> 
#include <stdio.h>
 
void eratosthenes(int top)
{
  int all[10000];
  int idx = 0;
  int prime = 3;
  int x, j;
 
  printf("1 ");
 
  while(prime <= top)
  {
    for(x = 0; x < top; x++)
    {
      if(all[x] == prime) goto skip; 
    }
 
    printf("%d ", prime);
    j = prime;
    while(j <= (top / prime))
    {
      all[idx++] = prime * j;
      j += 1;
    }
 
skip:	
    prime+=2;
  }
  puts("");
  return;
}
 
int main(int argc, char **argv)
{
  if(argc == 2) eratosthenes(atoi(argv[1]));
  else eratosthenes(50);
  return 0;
}

En lenguaje Fortran

*       Sieve of Eratosthenes by Chuck Bouldin
        top = 50
 
        logical*2 flags(top)
        integer*2 i,j,k,count,iter,prime
        n = long(362)                   
        do 92 iter = 1,10
           count=0
           i=0
           do 10 i = 1,top
10            flags(i) = .true.
           do 91 i = 1,top
              if (.not. flags(i)) go to 91
              prime = i + i + 3
              count = count + 1
              k = i + prime
              if (k .gt. top) go to 91
              do 60 j = k, top, prime
60               flags(j) = .false.
91          continue
92      continue
        write (9,*) count," primes in ",(long(362)-n)/60.0," seconds "
        pause
        end

En Lenguaje de programación Java

public class Eratosthenes 
{
    public static void main(String[] args) 
    { 
        int N = Integer.parseInt(args[0]);
 
        boolean[] isPrime = new boolean[N + 1];
        for (int i = 2; i <= N; i++)
            isPrime[i] = true;
 
        for (int i = 2; i*i <= N; i++) 
        {
            if (isPrime[i]) 
            {
                for (int j = i; i*j <= N; j++)
                    isPrime[i*j] = false;
            }
        }
 
        int primes = 0;
        for (int i = 2; i <= N; i++)
        {
           if (isPrime[i])
              System.out.println(" " + i);
        }
    }
}

En Lenguaje de programación Pascal

program Eratosthenes;
 
const N=1000;
 
var a:ARRAY[1..N] of boolean;
    i,j,m:word;
 
begin
 for i:=1 TO N do A[i]:=TRUE;
 m:=truncC(sqrt(N));
 for i:=2 to m do
   if a[i] then for j:=2 to N DIV i do a[i*j]:=FALSE;
 for i:=1 to N do if a[i] then write(i:4);
end.

En lenguaje Perl

#!/usr/bin/perl
$n = 50;  
for ( $i=1; $i<=$n; $i++ ) {
 $p[$i] = $i;
}                                    
$k = int( sqrt($n) );                
$i=2;
while ( $i <= $k ) {
 while ( $p[ $i ] == 0 ) {    
  $i ++;                                     
 }                                       
  for ( $j=2; $j<=$n; $j++ ) {                                     
  $a = $i * $j;
  $p[ $a ] = 0;                
 }                               
 $i++;
}                 
for ( $i=1; $i<=$n; $i++ ) {
 if ( $p[$i] != 0 ) {
  printf ( "%d\n", $p[$i] );
 }
}

En lenguaje PHP

 <?php
 
/* Sieve Of Erathosthenes by Denis Sureau */
 
function eratosthenes($n)
{
   $all=array();
   $prime=1;
   echo 1," ",2;
   $i=3;
   while($i<=$n)
   {
        if(!in_array($i,$all))
         {
            echo " ",$i;
            $prime+=1;
            $j=$i;
            while($j<=($n/$i))
            {
               array_push($all,$i*$j);
               $j+=1;
            }
         }
        $i+=2;
   }
   echo "\n";
   return;
}
 
eratosthenes(50);
?>

En lenguaje Ruby

# sieve of Eratosthenes from the ruby distro
top = Integer(ARGV.shift || 100)
sieve = []
for i in 2 .. top
  sieve[i] = i
end
 
for i in 2 .. Math.sqrt(top)
  next unless sieve[i]
  (i*i).step(top, i) do |j|
    sieve[j] = nil
  end
end
puts sieve.compact.join " "

En lenguaje Visual Basic .NET

Module Eratosthenes
    'Sieve of Eratosthenes by Marcelo Rivera
    Sub Main()
        Dim number As Integer
        number = 20
 
        Dim IsPrime(number) As Boolean
 
        For i As Integer = 2 To number
            If IsPrime(i - 1) = False Then
                For j As Integer = i To number / i
                    IsPrime((i * j) - 1) = True
                Next
            End If
        Next
 
        For x As Integer = 1 To number - 1
            If IsPrime(x) = False Then
                Console.WriteLine(x + 1)
            End If
        Next
    End Sub
End Module

[editar] Refinamiento

Una implementación más eficiente requiere crear un arreglo con solo los impares (pues los pares distintos de 2 ya se sabe que no son primos). En este caso se deben tachar los múltiplos impares de 3,4,5,...

Los múltiplos impares del primo $p = 2 i + 3$ son $(2 k + 1)(2 i + 3)$ . Debemos tachar desde $k = i + 1$ en adelante pues siempre se empieza a tachar desde $p 2$ . Note que si $k = i + 1$ entonces el primer múltiplo de $p = 2 i + 3$ es $(2 k + 1)(2 i + 3) = p 2$ .

Si corresponde tachar los múltiplos del primo $k -$ ésimo $p k$ , se inicia en $p_k^2$ pues antes de $p k$ , ya se han tachado $2 p k$ (los pares), $3 p k$ (los múltiplos de 3), $5 p k$ ,..., $p_{k-1}\cdot p_k$ .

Así, si $p_k^2>n$ ya no habría algo que tachar, por eso terminamos ahí el programa.

En la implementación se usa un arreglo "esPrimo()" tipo boolean. Aquí, "esPrimo(i)" representa al número impar $2 i + 3$ .

Note que si $p = 2 i + 3$ entonces $p$ está representado por "esPrimo((p-3)/2)".

Así, si se sabe que $p = 2 i + 3$ es primo, sus múltiplos (impares) no son primos, es decir, debemos poner

"esPrimo(((2k+1)p-3)/2)=false, k=i+1,i+2,..."

En la implementación iniciamos con el arreglo "esPrimo()" con todas sus entradas true. Iniciando en $p = 3$ , ponemos "esPrimo(((2k+1)3-3)/2)=false, k=0+1,0+2,..." y así sucesivamente: para cada nuevo $i$ primero preguntamos si "esPrimo(i)=true", si es así, "tachamos" sus múltiplos poniendo la respectiva entrada "false".

La siguiente función, en VBA, es una función que recibe $n$ y devuelve un arreglo con los primos $\leq n$ (ver más detalles en la segunda referencia)

 
Function ERATOSTENES(n) As Long()
Dim i, j, k, pos, contaPrimos
Dim max As Long
Dim esPrimo() As Boolean
Dim Primos() As Long
max = (n - 3) \ 2 ' División entera
ReDim esPrimo(max + 1)
ReDim Primos(max + 1)
For i = 0 To max
    esPrimo(i) = True
Next i
contaPrimos = 0
Primos(0) = 2 'contado el 2
j = 0
While (2 * j + 3)  <= n\(2 * j + 3)
    k = j + 1
    If esPrimo(j) Then
        While (2 * k + 1)   <= n\(2 * j + 3)
            pos = ((2 * k + 1) * (2 * j + 3) - 3) \ 2
            esPrimo(pos) = False
            k = k + 1
        Wend
    End If
j = j + 1
Wend
 
For i = 0 To max
   If esPrimo(i) Then
        contaPrimos = contaPrimos + 1 '3,5,...
        Primos(contaPrimos) = 2 * i + 3
    End If
Next i
 
ReDim Preserve Primos(contaPrimos) 'Cortamos el vector
ERATOSTENES = Primos()
End Function

[editar] Véase también

Test de primalidad

[editar] Referencias

Samuel Horsley (1772). « $KOΣKINON EPATOΣΘENOΥΣ$ . or, The Sieve of Eratosthenes. Being an Account of His Method of Finding All the Prime Numbers, by the Rev. Samuel Horsley, F. R. S.». Philosophical Transactions (1683-1775) 62.
Walter Mora F.. «Criba de Eratóstenes». Revista digital Matemática: Educación e Internet 7 (2).

Criba de Eratóstenes

De Wikipedia, la enciclopedia libre

Contenido

[editar] Proceso de criba

[editar] Pseudocódigo

[editar] Implementacion

[editar] Refinamiento

[editar] Véase también

[editar] Referencias

Vistas

Herramientas personales

Buscar

Navegación

Crear un libro

Herramientas

En otros idiomas