Implementación de algoritmos de teoría de números/Criba de Eratóstenes

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.

Pseudocódigo

Algoritmo:    Criba de Eratóstenes
Orden de complejidad:    ${\mathcal {O}}(n~\log n~\log \log n)$

Entrada: Un número natural $n$

Salida: El conjunto de números primos anteriores a $n$ (incluyendo $n$)

1. Escriba todos los números naturales desde $2$ hasta $n$
2. Para $i$ desde $2$ hasta $\lfloor {\sqrt {n}}\rfloor$ haga lo siguiente:
   1. Si $i$ no ha sido marcado entonces:
      1. Para $j$ desde $i$ hasta $n\div i$ haga lo siguiente:
         1. Ponga una marca en $i\times j$
3. El resultado es: Todos los números sin marcar.

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$

Implementación en distintos lenguajes 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;

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

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

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;
        }
    }
}

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;
        }
    }
}

C#

Versión 1

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace sieve
{
    class Program
    {
        static void Main(string[] args)
        {
            int maxprime = int.Parse(args[0]);
            ArrayList primelist = sieve(maxprime);
 
            foreach (int prime in primelist)
                Console.WriteLine(prime);
 
            Console.WriteLine("Count = " + primelist.Count);
            Console.ReadLine();
        }
 
        static ArrayList sieve(int arg_max_prime)
        {
            BitArray al = new BitArray(arg_max_prime, true);
 
            int lastprime = 1;
            int lastprimeSquare = 1;
 
            while (lastprimeSquare <= arg_max_prime)
            {
                lastprime++;
 
                while (!(bool)al[lastprime])
                    lastprime++;
 
                lastprimeSquare = lastprime * lastprime;
 
                for (int i = lastprimeSquare; i < arg_max_prime; i += lastprime)
                    if (i > 0)
                        al[i] = false;
            }
 
            ArrayList sieve_2_return = new ArrayList();
 
            for (int i = 2; i < arg_max_prime; i++)
                if (al[i])
                    sieve_2_return.Add(i);
 
            return sieve_2_return;
        }
    }
}

Versión 2

using System;
using System.Text;

namespace Primalidad
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = 101; // número máximo hasta el que se quiere calcular
            bool[] marcados = new bool[n+1];
            StringBuilder builder = new StringBuilder();

            for (int i = 2; i <= Math.Sqrt(n); i++) {
                if (!marcados[i])
                    for (int j = i*2; j <= n; j += i)
                        marcados[j] = true; // se marcan los que se sabe que NO son primos
            }

            for (int i = 2; i < marcados.Length; i++)
                if (marcados[i] == false) // los primos son los que no están marcados
                    builder.Append(i + ", ");
            builder.Length -= 2;
            Console.WriteLine("Los número primos hasta el número " + n + " son: "+builder);

            Console.WriteLine();
            Console.WriteLine("Pulse enter para salir");
            Console.ReadLine();
        }
    }
}

Fortran

        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

Haskell

Versión 1

eratostenes :: [Int] -> [Int] -- Criba de Eratóstenes (de una lista dada [2..n] te deja sólo los números primos)
eratostenes [] = []
eratostenes (x:xs) | not (null xs) && x^2 > last xs = (x:xs)
                   | otherwise = x: eratostenes [y | y <- xs, y `mod` x /= 0]

Versión 2

erastotenes ::  Int -> [Int]
erastotenes n = erastotenes2 [x|x <- [2..n]] 0

erastotenes2 :: [Int] -> Int -> [Int]
erastotenes2 lista n 
		| n == length lista-1 = lista
		|otherwise=erastotenes2 [x|x <-lista,(x `mod` lista!!n)/=0||x==lista!!n] (n+1)

Java

import java.util.ArrayList;
import java.util.List;

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);
		}
	}
	
}

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.

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] );
 }
}

PHP

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);

Python

Python 3:

 
def criba_eratostenes(n):
  multiplos = set()
  for i in range(2, n+1):
    if i not in multiplos:
      print(i, end=" ")
      multiplos.update(range(i*i, n+1, i))

criba_eratostenes(1000)

R

primos<-function(n){
  posibles<-seq(1,n,by=2)
  posibles[1]<-2
  for(i in 2:round(sqrt(n))){
    if(posibles[i]!=0){
      for(j in seq(i + posibles[i], n/2, by=posibles[i])){
        posibles[j]<-0
      }
    }
  }
  return(posibles[posibles!=0])
}
primos(10000)

Ruby

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

Visual Basic .NET

Module Eratosthenes

    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