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[editar]
Algoritmo: Criba de Eratóstenes
Orden de complejidad:
Entrada: Un número natural
Salida: El conjunto de números primos anteriores a (incluyendo )
- Escriba todos los números naturales desde hasta
- Para desde hasta haga lo siguiente:
- Si no ha sido marcado entonces:
- Para desde hasta haga lo siguiente:
- Ponga una marca en
- Para desde hasta haga lo siguiente:
- Si no ha sido marcado entonces:
- El resultado es: Todos los números sin marcar.
Acerca de la notación:
- es la función parte entera de
- es el cociente de dividir entre
Implementación en distintos lenguajes de programación[editar]
Ada[editar]
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[editar]
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[editar]
#!/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[editar]
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++[editar]
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#[editar]
Versión 1[editar]
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[editar]
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[editar]
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[editar]
Versión 1[editar]
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[editar]
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[editar]
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[editar]
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[editar]
#!/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[editar]
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[editar]
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[editar]
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[editar]
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[editar]
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