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] 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:de dos en dos asi sucesivamente 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] Código

En lenguaje Haskell

eratostenes :: [Int] -> [Int] -- Criba de eratostenes (de una lista dada [2..n] t deja solo los numeros primos)
eratostenes [] = []
eratostenes (x:xs) | not (null xs) && x^2 > last xs = (x:xs)
                   | otherwise = x: eratostenes [y | y <- xs, y `mod` x /= 0]

En lenguaje Python

 
#!/usr/bin/python
# -*- coding: UTF-8 -*-
# Contribución por David Alessandro Falconi Concordia.
nums=[]
prims=[]
num=input(">>> ")
for i in range(2, num+1):
        nums.append(i)
while nums != []:
        n=nums[0]
        prims.append(n)
        n=(float(n))
        for j in nums:
                if ((j % n ) == 0.0):
                        nums.remove(j)
print prims

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 C

void criba(unsigned char m[], int tam){
    int i, h;
 
    m[0] = 0;
    m[1] = 0;
    for(i = 2; i <= tam; ++i) m[i] = 1;
 
    for(i = 2; i*i <= tam; ++i) {
        if(m[i]) {
            for(h = 2; i*h <= tam; ++h)
                m[i*h] = 0;
        }
    }
}

En lenguaje C++

void criba(bool m[], int tam){
    m[0] = false;
    m[1] = false;
    for(int i = 2; i <= tam; ++i) m[i] = true;
 
    for(int i = 2; i*i <= tam; ++i) {
        if(m[i]) {
            for(int h = 2; i*h <= tam; ++h)
                m[i*h] = false;
        }
    }
}

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

import java.util.ArrayList;
import java.util.List;
 
/**
 * Criba de Eratostenes (Mejorado)
 * 
 * Generacion de los n primeros primos mediante el algoritmo
 * de la criba de Eratostenes
 *
 * Requiere Java 5
 */
public class EratostenesMejorado {
 
        public static void main(String[] args) {
                int n = Integer.parseInt(args[0]);
                int tope = (int) Math.floor(Math.sqrt(n)) + 1;
 
                List<Long> compuestos = new ArrayList<Long>();
                int pos = 0;
                for (int i = 2; i <= tope; i++) {
                        if (!compuestos.contains(Long.valueOf(i))) {
                                for (int j = i; j <= n / i + 1; j++)
                                        compuestos.add(Long.valueOf(i * j));
                        }
                }
 
                int c = 0;
                for (pos = 2; pos < n; pos++) {
                        if (!compuestos.contains(Long.valueOf(pos)))
                                System.out.println(++c + ": " + pos);
                }
        }
 
}

En Lenguaje de programación Java (Opcion 2 JAOC USC)

import java.util.ArrayList;
import java.util.Scanner;
import java.util.List;
 
public class CribaDeEratostenes_NumerosPrimos {
 
        List<Integer> num = new ArrayList<Integer>();
 
        public void llenarVector(int numFinal) {
                if(numFinal==0)
                        System.out.println("\n\n**********  Gracias  **********");
        else if (numFinal>=3)
                {
                        int n = 3;
                        do {
                                num.add(n);
                                n = n + 2;
                        } while (n <= numFinal);
 
                        System.out
                                        .println("\n******  Listado de numeros impares a partir del 3  ******\n");
                        for (int i = 0; i < num.size(); i++)
                                System.out.println(i + 1 + " : " + num.get(i));
                        primos();
                }
                else
                        System.out.println("\n\n**********  El numero a digitar debe ser mayor que 2  **********\n\n");
        }
 
        public void primos() {
                List<Integer> numSelect = new ArrayList<Integer>();
                int aux;
                int i = 0;
                do {
                        aux = num.get(i);
                        if (aux != 0 && numSelect.contains(aux) == false) {
 
                                numSelect.add(aux);
                                int z = i;
                                for (z = i + aux; z < num.size(); z = z + aux) {
                                        // System.out.println("Z : "+z+" num = "+num.get(z)+" N = "+aux);
                                        num.set(z, 0);
                                }
 
                                // System.out.println("i = "+i);
                        }
                        i++;
 
                } while (i < num.size());
 
                System.out
                                .println("\n"
                                                + "******************  RESULTADOS ==>> NUM. PRIMOS  ******************"
                                                + "\n");
                int y = 1;
                for (int t = 0; t < num.size(); t++) {
 
                        if (num.get(t) != 0) {
                                System.out.println(y + " : " + num.get(t));
                                y++;
                        }
 
                }
 
        }
 
        public static void main(String[] Args) {
 
                Scanner ingreso = new Scanner(System.in);
                int numLimite;
                do
                {
                        System.out.println("Para salir escribe 0");
                        System.out.println("Numeros primos desde 3 hasta: ");
                        numLimite = Integer.parseInt(ingreso.nextLine());
                        CribaDeEratostenes_NumerosPrimos p = new CribaDeEratostenes_NumerosPrimos();
                        p.llenarVector(numLimite);
                }while(numLimite!=0);
 
        }
 
}

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:=trunc(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,7

Los múltiplos impares del primo $p =2i+3$ son $(2k+1)(2i+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 =2i+3$ es $(2k+1)(2i+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 $2p_k$ (los pares), $3p_k$ (los múltiplos de 3), $5p_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 $2i+3$ .

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

Así, si se sabe que $p=2i+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

En Lenguaje de Programación Java

import javax.swing.JOptionPane;
public class Erastostenes
{
   public static void main( String args[] )
   {
      // Contribución de David Jesús ( UNMSM - FISI )
      int N = Integer.parseInt( JOptionPane.showInputDialog( "Limite superior :" ) );
 
      int k, pos;
      int numMaxPrimos = ( N - 3 ) / 2 ;
      int numPrimos = 0;
 
      int[] Primos = new int[ numMaxPrimos + 1 ];       
      boolean[] esPrimo = new boolean[ numMaxPrimos + 1 ];
 
      for( int i = 0; i < numMaxPrimos; i ++ )
         esPrimo[ i ] = true;
 
      for( int i = 0; i*i < N; i ++ )
      {
         k = i + 1;
         if( esPrimo[ i ] )
         {
            for( k = i + 1; ( 2 * k + 1 ) * ( 2 * i + 3 ) <= N; k ++ )
            {
               pos = ( ( 2 * k + 1 ) * ( 2 * i + 3 ) - 3 ) / 2;
               esPrimo[ pos ] = false;
            }
         }
      } 
 
      // Mostramos y a la vez guardamos los numeros primos en el vector 
      Primos[ 0 ] = 2;
      System.out.print( "  2" );
 
      for(  int i = 0; i <= numMaxPrimos; i ++ )
      {
         if( esPrimo[ i ] )
         {
            numPrimos ++;
            Primos[ numPrimos ] = 2 * i + 3;
            System.out.print( "  " + Primos[ numPrimos ] );
         }
      }
   }
}

[editar] Véase también

Test de primalidad

[editar] Referencias

Samuel Horsley (1772). « $\text{KO}\Sigma \text{KINON EPATO}\Sigma \Theta \text{ENO}\Upsilon \Sigma$ . 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. http://links.jstor.org/sici?sici=0260-7085(1772)62%3C327%3AOTSOEB%3E2.0.CO%3B2-5.
Walter Mora F.. «Criba de Eratóstenes». Revista digital Matemática: Educación e Internet 7 (2). http://www.cidse.itcr.ac.cr/revistamate/HERRAmInternet/Criba/Criba.pdf.

Criba de Eratóstenes

Contenido

[editar] Pseudocódigo

[editar] Código

[editar] Refinamiento

[editar] Véase también

[editar] Referencias

Herramientas personales

Espacios de nombres

Variantes

Vistas

Acciones

Buscar

Navegación

Imprimir/exportar

Herramientas

En otros idiomas