Wikilibros

Diferencia entre revisiones de «Implementación de algoritmos de teoría de números/Criba de Eratóstenes»

Explorar historial interactivamente
← Edición anteriorEdición siguiente →
Contenido eliminado Contenido añadido
VisualWikitexto
Götz (discusión | contribs.)
10 ediciones
Actualizado desde w:Criba de Eratóstenes oldid=60178082; orden alfabético, encabezados nivel 3; arreglos menores.
Línea 16:
#### Ponga una marca en <math>i\times j</math>
# '''El resultado es:''' Todos los números sin marca
<br />
== Implementación en lenguajes de programación ==
 
== Implementación en distintos lenguajes de programación ==
== En Haskell ==
 
<source lang="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]
</source>
 
== En Python ==
 
<source lang="Python">
#Criba de Erastostenes por Calvo
from math import sqrt,floor
 
n=float(raw_input('Introduzca un valor N: '))
d=set()
p=2,
 
for i in range(2,floor(sqrt(n))+1):
if i not in d:
for j in range(i,n/i+1): d.add(i*j)
 
for i in range(n,1,-1):
if i not in d: print i
</source>
 
== En Ada ==
 
=== Ada ===
<source lang="Ada">
procedure Eratosthenes(Result : out Integer) is
Línea 82 ⟶ 54:
</source>
 
=== En BasicBASIC ===
 
<source lang="vb">
defint a-z
Línea 105 ⟶ 76:
</source>
 
== En= Bash ===
 
<source lang="Bash">
#!/bin/bash
Línea 131 ⟶ 101:
</source>
 
== En= C# ===
<source lang="c">
 
void criba(unsigned char m[], int tam){
<source lang="csharp">
// Iker Ruiz Arnauda - 2012
// Sieve of Eratosthenes - C#
// Criba de Eratóstenes - C#
// This program will calculate prime numbers based on Eratosthenes algorithm,
// the result will be dumped into a txt file considering you use this to extract primes from a wide range.
 
using System;
using System.Collections.Generic;
using System.Threading.Tasks;
using System.IO;
using System.Threading;
 
namespace Main
{
class Program
{
static void Main(String[] Args)
{
Int32 primeFoundCounter = 0;
Boolean ended = false;
do
{
Console.WriteLine("Type the upper limit (Positive Intiger):");
try
{
//Read size of the array from the user, convert it to an Intiger.
var SuperiorLimit = Convert.ToInt32(Console.ReadLine());
Console.Clear();
//Create the array.
Boolean[] primesArray = new Boolean[SuperiorLimit];
//Fill the boolean array, set all false by default.
for (Int32 i = 2; i < SuperiorLimit; i++)
primesArray[i] = false;
 
for (Int32 i = 2; i < Math.Sqrt(SuperiorLimit); i++)
{
if (!primesArray[i])
{
for (Int32 k = 2; i * k < SuperiorLimit; k++)
{
//Found prime, set the value truth.
primesArray[(i * k)] = true;
}
}
}
 
//Save Results into a txt file on users desktop.
string OutputPath = Environment.GetFolderPath(Environment.SpecialFolder.Desktop);
using (StreamWriter sw = new StreamWriter(OutputPath + @"\Primes.txt"))
{
for (int j = 2; j < primesArray.Length; j++)
{
if (!primesArray[j])
{
sw.WriteLine("[" + j + "] ");
primeFoundCounter++;
}
}
sw.Close();
}
 
Console.ForegroundColor = ConsoleColor.Yellow;
Console.WriteLine("Found " + primeFoundCounter + " prime numbers");
Console.ForegroundColor = ConsoleColor.Green;
Console.WriteLine("Results were saved into: " + OutputPath + "\\Primes.txt.");
Console.ForegroundColor = ConsoleColor.White;
Console.WriteLine("Press any key to exit...");
 
//Operation completed succesfully, we kill the loop.*/
ended = true;
Console.Read();
}
//If the operation fail, show the error to the user and let him try again.
catch (Exception ex)
{
Console.WriteLine("[ERROR] " + ex.Message);
Console.WriteLine("Press enter to try again...");
Console.ReadLine();
Console.Clear();
}
} while (!ended);
}
}
}
</source>
 
== En C ==
<source lang="c">void criba(unsigned char m[], int tam){
int i, h;
 
Línea 237 ⟶ 119:
</source>
 
== En= C++ ===
<source lang="cpp">
 
<source lang="cpp">void criba(bool m[], int tam){
m[0] = false;
m[1] = false;
Línea 253 ⟶ 135:
</source>
 
=== En FortranC# ===
<source lang="csharp">
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;
}
}
}
</source>
 
=== Fortran ===
<source lang="Fortran">
* Sieve of Eratosthenes by Chuck Bouldin
top = 50
 
Línea 282 ⟶ 219:
</source>
 
=== En JavaHaskell ===
<source lang="Haskell">
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]
</source>
 
=== Java ===
<source lang="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 {
 
Línea 321 ⟶ 257:
</source>
 
=== EnJava Pascal(opción 2 JAOC USC) ===
<source lang="Java">
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);
}
 
}
</source>
 
=== Pascal ===
<source lang="Pascal">
program Eratosthenes;
Línea 340 ⟶ 361:
</source>
 
== En= Perl ===
 
<source lang="Perl">
#!/usr/bin/perl
Línea 367 ⟶ 387:
</source>
 
== En= PHP ===
 
<source lang="PHP">
<?php
 
/* Sieve Of Erathosthenes by Denis Sureau */
 
function eratosthenes($n)
{
Línea 400 ⟶ 415:
 
eratosthenes(50);
?>
</source>
 
=== En RubyPython ===
Python 3:
<source lang="Python">
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)
</source>
 
=== Ruby ===
<source lang="Ruby">
# sieve of Eratosthenes from the ruby distro
top = Integer(ARGV.shift || 100)
sieve = []
Línea 422 ⟶ 447:
</source>
 
== En= Visual Basic .NET ===
 
<source lang="vbnet">
Module Eratosthenes
 
'Sieve of Eratosthenes by Marcelo Rivera
Sub Main()
Dim number As Integer
Obtenido de «https://es.wikibooks.org/wiki/Implementación_de_algoritmos_de_teoría_de_números/Criba_de_Eratóstenes»