c# - para - como sacar los numeros primos del 1 al 100
La manera más elegante de generar números primos (25)
Aquí hay un ejemplo de código python que imprime la suma de todos los primos por debajo de dos millones:
from math import *
limit = 2000000
sievebound = (limit - 1) / 2
# sieve only odd numbers to save memory
# the ith element corresponds to the odd number 2*i+1
sieve = [False for n in xrange(1, sievebound + 1)]
crosslimit = (int(ceil(sqrt(limit))) - 1) / 2
for i in xrange(1, crosslimit):
if not sieve[i]:
# if p == 2*i + 1, then
# p**2 == 4*(i**2) + 4*i + 1
# == 2*i * (i + 1)
for j in xrange(2*i * (i + 1), sievebound, 2*i + 1):
sieve[j] = True
sum = 2
for i in xrange(1, sievebound):
if not sieve[i]:
sum = sum + (2*i+1)
print sum
¿Cuál es la forma más elegante de implementar esta función?
ArrayList generatePrimes(int n)
Esta función genera los primeros n primos (edit: donde n>1 ), por lo que generatePrimes(5) devolverá una ArrayList con {2, 3, 5, 7, 11} . (Estoy haciendo esto en C #, pero estoy contento con una implementación de Java, o cualquier otro lenguaje similar para ese asunto (por lo que no es Haskell)).
Sé cómo escribir esta función, pero cuando lo hice anoche no terminó tan bien como esperaba. Aquí es lo que se me ocurrió:
ArrayList generatePrimes(int toGenerate)
{
ArrayList primes = new ArrayList();
primes.Add(2);
primes.Add(3);
while (primes.Count < toGenerate)
{
int nextPrime = (int)(primes[primes.Count - 1]) + 2;
while (true)
{
bool isPrime = true;
foreach (int n in primes)
{
if (nextPrime % n == 0)
{
isPrime = false;
break;
}
}
if (isPrime)
{
break;
}
else
{
nextPrime += 2;
}
}
primes.Add(nextPrime);
}
return primes;
}
No estoy demasiado preocupado por la velocidad, aunque no quiero que sea obviamente ineficiente. No me importa qué método se use (ingenuo o tamiz o cualquier otra cosa), pero sí quiero que sea bastante breve y obvio cómo funciona.
Editar : Gracias a todos los que respondieron, aunque muchos no respondieron mi pregunta real. Para reiterar, quería un buen código limpio que generara una lista de números primos. Ya sé cómo hacerlo de diferentes maneras, pero soy propenso a escribir código que no es tan claro como podría ser. En este hilo, se han propuesto algunas buenas opciones:
- Una versión más bonita de lo que originalmente tuve (Peter Smit, jmservera y Rekreativc)
- Una implementación muy limpia del tamiz de Eratóstenes (starblue)
- Utilice
BigIntegers de Java ynextProbablePrimepara un código muy simple, aunque no puedo imaginar que sea particularmente eficiente (dfa) - Use LINQ para generar perezadamente la lista de primos (Maghis)
- Coloca muchos primos en un archivo de texto y léelos cuando sea necesario (darin)
Edición 2 : he implementado en C # algunos de los métodos que se dan aquí, y otro método que no se menciona aquí. Todos encuentran los primeros n primos de manera efectiva (y tengo un método decente para encontrar el límite para proporcionar a los tamices).
Aquí hay una implementación de Sieve of Eratosthenes en C #:
IEnumerable<int> GeneratePrimes(int n)
{
var values = new Numbers[n];
values[0] = Numbers.Prime;
values[1] = Numbers.Prime;
for (int outer = 2; outer != -1; outer = FirstUnset(values, outer))
{
values[outer] = Numbers.Prime;
for (int inner = outer * 2; inner < values.Length; inner += outer)
values[inner] = Numbers.Composite;
}
for (int i = 2; i < values.Length; i++)
{
if (values[i] == Numbers.Prime)
yield return i;
}
}
int FirstUnset(Numbers[] values, int last)
{
for (int i = last; i < values.Length; i++)
if (values[i] == Numbers.Unset)
return i;
return -1;
}
enum Numbers
{
Unset,
Prime,
Composite
}
Copyrights 2009 por St.Wittum 13189 Berlin ALEMANIA bajo la licencia CC-BY-SA https://creativecommons.org/licenses/by-sa/3.0/
La manera simple pero más elegante de calcular TODOS PRIMES sería esta, pero de esta manera es lenta y los costos de memoria son mucho más altos para números más altos porque usa la función de facultad (!) ... pero demuestra una variación de Wilson Theoreme en una aplicación a generar todos los primos por algoritmo implementado en Python
#!/usr/bin/python
f=1 # 0!
p=2 # 1st prime
while True:
if f%p%2:
print p
p+=1
f*=(p-2)
De ninguna manera eficiente, pero tal vez la más legible:
public static IEnumerable<int> GeneratePrimes()
{
return Range(2).Where(candidate => Range(2, (int)Math.Sqrt(candidate)))
.All(divisor => candidate % divisor != 0));
}
con:
public static IEnumerable<int> Range(int from, int to = int.MaxValue)
{
for (int i = from; i <= to; i++) yield return i;
}
De hecho, solo una variación de algunas publicaciones aquí con un formato más agradable.
Deberías echarle un vistazo a los números primos probables . En particular, eche un vistazo a los algoritmos aleatorizados y la prueba de primalidad Miller-Rabin .
En aras de la exhaustividad, puedes usar java.math.BigInteger :
public class PrimeGenerator implements Iterator<BigInteger>, Iterable<BigInteger> {
private BigInteger p = BigInteger.ONE;
@Override
public boolean hasNext() {
return true;
}
@Override
public BigInteger next() {
p = p.nextProbablePrime();
return p;
}
@Override
public void remove() {
throw new UnsupportedOperationException("Not supported.");
}
@Override
public Iterator<BigInteger> iterator() {
return this;
}
}
@Test
public void printPrimes() {
for (BigInteger p : new PrimeGenerator()) {
System.out.println(p);
}
}
El método más simple es la prueba y el error: intente si cualquier número entre 2 y n-1 divide su candidato principal n.
Los primeros atajos son, por supuesto, a) solo tienes que marcar números impares, yb) solo tienes que verificar los divisores hasta sqrt (n).
En su caso, donde también genera todos los primos previos en el proceso, solo tiene que verificar si alguno de los números primos en su lista, hasta sqrt (n), divide n.
Debería ser el más rápido que puedas obtener por tu dinero :-)
editar
Ok, código, lo pediste. Pero te lo advierto :-), este es el código Delphi de 5 minutos: rápido y sucio:
procedure TForm1.Button1Click(Sender: TObject);
const
N = 100;
var
PrimeList: TList;
I, J, SqrtP: Integer;
Divides: Boolean;
begin
PrimeList := TList.Create;
for I := 2 to N do begin
SqrtP := Ceil(Sqrt(I));
J := 0;
Divides := False;
while (not Divides) and (J < PrimeList.Count)
and (Integer(PrimeList[J]) <= SqrtP) do begin
Divides := ( I mod Integer(PrimeList[J]) = 0 );
inc(J);
end;
if not Divides then
PrimeList.Add(Pointer(I));
end;
// display results
for I := 0 to PrimeList.Count - 1 do
ListBox1.Items.Add(IntToStr(Integer(PrimeList[I])));
PrimeList.Free;
end;
Escribí una implementación simple de Eratosthenes en c # usando algún LINQ.
Lamentablemente, LINQ no proporciona una secuencia infinita de entradas, por lo que debe usar int.MaxValue :(
Tuve que guardar en caché de forma anónima el sqrt candidato para evitar calcularlo para cada primado en caché (se ve un poco feo).
Uso una lista de primos anteriores hasta sqrt del candidato
cache.TakeWhile(c => c <= candidate.Sqrt)
y comprueba cada Int comenzando desde 2 en contra
.Any(cachedPrime => candidate.Current % cachedPrime == 0)
Aquí está el código:
static IEnumerable<int> Primes(int count)
{
return Primes().Take(count);
}
static IEnumerable<int> Primes()
{
List<int> cache = new List<int>();
var primes = Enumerable.Range(2, int.MaxValue - 2).Select(candidate => new
{
Sqrt = (int)Math.Sqrt(candidate), // caching sqrt for performance
Current = candidate
}).Where(candidate => !cache.TakeWhile(c => c <= candidate.Sqrt)
.Any(cachedPrime => candidate.Current % cachedPrime == 0))
.Select(p => p.Current);
foreach (var prime in primes)
{
cache.Add(prime);
yield return prime;
}
}
Otra optimización es evitar el control de números pares y devolver solo 2 antes de crear la Lista. De esta forma, si el método de llamada solo solicita 1 primo evitará todo el desorden:
static IEnumerable<int> Primes()
{
yield return 2;
List<int> cache = new List<int>() { 2 };
var primes = Enumerable.Range(3, int.MaxValue - 3)
.Where(candidate => candidate % 2 != 0)
.Select(candidate => new
{
Sqrt = (int)Math.Sqrt(candidate), // caching sqrt for performance
Current = candidate
}).Where(candidate => !cache.TakeWhile(c => c <= candidate.Sqrt)
.Any(cachedPrime => candidate.Current % cachedPrime == 0))
.Select(p => p.Current);
foreach (var prime in primes)
{
cache.Add(prime);
yield return prime;
}
}
Estás en el buen camino.
Algunos comentarios
primos.Agregar (3); hace que esta función no funcione para number = 1
No es necesario probar la división con primenumbers más grandes que la raíz cuadrada del número que se probará.
Código sugerido:
ArrayList generatePrimes(int toGenerate)
{
ArrayList primes = new ArrayList();
if(toGenerate > 0) primes.Add(2);
int curTest = 3;
while (primes.Count < toGenerate)
{
int sqrt = (int) Math.sqrt(curTest);
bool isPrime = true;
for (int i = 0; i < primes.Count && primes.get(i) <= sqrt; ++i)
{
if (curTest % primes.get(i) == 0)
{
isPrime = false;
break;
}
}
if(isPrime) primes.Add(curTest);
curTest +=2
}
return primes;
}
Este es el más elegante que puedo pensar en poco tiempo.
ArrayList generatePrimes(int numberToGenerate)
{
ArrayList rez = new ArrayList();
rez.Add(2);
rez.Add(3);
for(int i = 5; rez.Count <= numberToGenerate; i+=2)
{
bool prime = true;
for (int j = 2; j < Math.Sqrt(i); j++)
{
if (i % j == 0)
{
prime = false;
break;
}
}
if (prime) rez.Add(i);
}
return rez;
}
Espero que esto ayude a darte una idea. Estoy seguro de que esto se puede optimizar, sin embargo, debería darle una idea de cómo su versión podría hacerse más elegante.
EDITAR: Como se señaló en los comentarios, este algoritmo de hecho devuelve valores incorrectos para numberToGenerate <2. Solo quiero señalar que no estaba tratando de publicar un gran método para generar números primos (mire la respuesta de Henri para eso), Yo estaba muy señalando cómo su método podría hacerse más elegante.
Esto lo obtuve en la primera lectura de "Sieve of Atkin" en Wikki, más algunas reflexiones previas que he dado a esto: dedico mucho tiempo a codificar desde cero y me concentro por completo en la crítica de mi compilación, codificación muy densa estilo + Ni siquiera hice el primer intento de ejecutar el código ... muchos de los paradigmas que aprendí a usar están aquí, solo lea y llore, obtenga lo que pueda.
Asegúrese absoluta y totalmente de probar todo esto antes de cualquier uso, seguro que no se lo muestre a nadie, es para leer y considerar las ideas. Necesito hacer funcionar la herramienta de primalidad, así que aquí es donde comienzo cada vez que tengo que hacer que funcione algo.
Obtenga una compilación limpia, luego empiece a quitar lo que está defectuoso - Tengo casi 108 millones de teclas de código utilizable haciéndolo de esta manera, ... use lo que pueda.
Trabajaré en mi versión mañana.
package demo;
// This code is a discussion of an opinion in a technical forum.
// It''s use as a basis for further work is not prohibited.
import java.util.Arrays;
import java.util.HashSet;
import java.util.ArrayList;
import java.security.GeneralSecurityException;
/**
* May we start by ignores any numbers divisible by two, three, or five
* and eliminate from algorithm 3, 5, 7, 11, 13, 17, 19 completely - as
* these may be done by hand. Then, with some thought we can completely
* prove to certainty that no number larger than square-root the number
* can possibly be a candidate prime.
*/
public class PrimeGenerator<T>
{
//
Integer HOW_MANY;
HashSet<Integer>hashSet=new HashSet<Integer>();
static final java.lang.String LINE_SEPARATOR
=
new java.lang.String(java.lang.System.getProperty("line.separator"));//
//
PrimeGenerator(Integer howMany) throws GeneralSecurityException
{
if(howMany.intValue() < 20)
{
throw new GeneralSecurityException("I''m insecure.");
}
else
{
this.HOW_MANY=howMany;
}
}
// Let us then take from the rich literature readily
// available on primes and discount
// time-wasters to the extent possible, utilizing the modulo operator to obtain some
// faster operations.
//
// Numbers with modulo sixty remainder in these lists are known to be composite.
//
final HashSet<Integer> fillArray() throws GeneralSecurityException
{
// All numbers with modulo-sixty remainder in this list are not prime.
int[]list1=new int[]{0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,
32,34,36,38,40,42,44,46,48,50,52,54,56,58}; //
for(int nextInt:list1)
{
if(hashSet.add(new Integer(nextInt)))
{
continue;
}
else
{
throw new GeneralSecurityException("list1");//
}
}
// All numbers with modulo-sixty remainder in this list are are
// divisible by three and not prime.
int[]list2=new int[]{3,9,15,21,27,33,39,45,51,57};
//
for(int nextInt:list2)
{
if(hashSet.add(new Integer(nextInt)))
{
continue;
}
else
{
throw new GeneralSecurityException("list2");//
}
}
// All numbers with modulo-sixty remainder in this list are
// divisible by five and not prime. not prime.
int[]list3=new int[]{5,25,35,55};
//
for(int nextInt:list3)
{
if(hashSet.add(new Integer(nextInt)))
{
continue;
}
else
{
throw new GeneralSecurityException("list3");//
}
}
// All numbers with modulo-sixty remainder in
// this list have a modulo-four remainder of 1.
// What that means, I have neither clue nor guess - I got all this from
int[]list4=new int[]{1,13,17,29,37,41,49,53};
//
for(int nextInt:list4)
{
if(hashSet.add(new Integer(nextInt)))
{
continue;
}
else
{
throw new GeneralSecurityException("list4");//
}
}
Integer lowerBound=new Integer(19);// duh
Double upperStartingPoint=new Double(Math.ceil(Math.sqrt(Integer.MAX_VALUE)));//
int upperBound=upperStartingPoint.intValue();//
HashSet<Integer> resultSet=new HashSet<Integer>();
// use a loop.
do
{
// One of those one liners, whole program here:
int aModulo=upperBound % 60;
if(this.hashSet.contains(new Integer(aModulo)))
{
continue;
}
else
{
resultSet.add(new Integer(aModulo));//
}
}
while(--upperBound > 20);
// this as an operator here is useful later in your work.
return resultSet;
}
// Test harness ....
public static void main(java.lang.String[] args)
{
return;
}
}
//eof
Lo hice en Java usando una biblioteca funcional que escribí, pero como mi biblioteca usa los mismos conceptos que Enumerations, estoy seguro de que el código es adaptable:
Iterable<Integer> numbers = new Range(1, 100);
Iterable<Integer> primes = numbers.inject(numbers, new Functions.Injecter<Iterable<Integer>, Integer>()
{
public Iterable<Integer> call(Iterable<Integer> numbers, final Integer number) throws Exception
{
// We don''t test for 1 which is implicit
if ( number <= 1 )
{
return numbers;
}
// Only keep in numbers those that do not divide by number
return numbers.reject(new Functions.Predicate1<Integer>()
{
public Boolean call(Integer n) throws Exception
{
return n > number && n % number == 0;
}
});
}
});
Muchas gracias a todos los que dieron respuestas útiles. Aquí están mis implementaciones de algunos métodos diferentes para encontrar los primeros n primos en C #. Los primeros dos métodos son más o menos lo que se publicó aquí. (Los nombres de los carteles están al lado del título.) Planeo hacer el tamiz de Atkin en algún momento, aunque sospecho que no será tan simple como los métodos aquí actualmente. Si alguien puede ver alguna forma de mejorar cualquiera de estos métodos, me encantaría saber :-)
Método estándar ( Peter Smit , jmservera , Rekreativc )
El primer número primo es 2. Agregue esto a una lista de números primos. El próximo primo es el siguiente número que no es divisible de manera pareja por ningún número en esta lista.
public static List<int> GeneratePrimesNaive(int n)
{
List<int> primes = new List<int>();
primes.Add(2);
int nextPrime = 3;
while (primes.Count < n)
{
int sqrt = (int)Math.Sqrt(nextPrime);
bool isPrime = true;
for (int i = 0; (int)primes[i] <= sqrt; i++)
{
if (nextPrime % primes[i] == 0)
{
isPrime = false;
break;
}
}
if (isPrime)
{
primes.Add(nextPrime);
}
nextPrime += 2;
}
return primes;
}
Esto se ha optimizado solo probando la divisibilidad hasta la raíz cuadrada del número que se prueba; y solo probando números impares. Esto se puede optimizar aún más probando solo números de la forma 6k+[1, 5] o 30k+[1, 7, 11, 13, 17, 19, 23, 29] etc.
Tamiz de Eratóstenes ( starblue )
Esto encuentra todos los primos en k . Para hacer una lista de los primeros n primos, primero necesitamos aproximar el valor de la n th prime. El siguiente método, como se describe aquí , hace esto.
public static int ApproximateNthPrime(int nn)
{
double n = (double)nn;
double p;
if (nn >= 7022)
{
p = n * Math.Log(n) + n * (Math.Log(Math.Log(n)) - 0.9385);
}
else if (nn >= 6)
{
p = n * Math.Log(n) + n * Math.Log(Math.Log(n));
}
else if (nn > 0)
{
p = new int[] { 2, 3, 5, 7, 11 }[nn - 1];
}
else
{
p = 0;
}
return (int)p;
}
// Find all primes up to and including the limit
public static BitArray SieveOfEratosthenes(int limit)
{
BitArray bits = new BitArray(limit + 1, true);
bits[0] = false;
bits[1] = false;
for (int i = 0; i * i <= limit; i++)
{
if (bits[i])
{
for (int j = i * i; j <= limit; j += i)
{
bits[j] = false;
}
}
}
return bits;
}
public static List<int> GeneratePrimesSieveOfEratosthenes(int n)
{
int limit = ApproximateNthPrime(n);
BitArray bits = SieveOfEratosthenes(limit);
List<int> primes = new List<int>();
for (int i = 0, found = 0; i < limit && found < n; i++)
{
if (bits[i])
{
primes.Add(i);
found++;
}
}
return primes;
}
Tamiz de Sundaram
Recientemente descubrí este tamiz , pero puede implementarse de manera sencilla. Mi implementación no es tan rápida como el tamiz de Eratóstenes, pero es significativamente más rápido que el método ingenuo.
public static BitArray SieveOfSundaram(int limit)
{
limit /= 2;
BitArray bits = new BitArray(limit + 1, true);
for (int i = 1; 3 * i + 1 < limit; i++)
{
for (int j = 1; i + j + 2 * i * j <= limit; j++)
{
bits[i + j + 2 * i * j] = false;
}
}
return bits;
}
public static List<int> GeneratePrimesSieveOfSundaram(int n)
{
int limit = ApproximateNthPrime(n);
BitArray bits = SieveOfSundaram(limit);
List<int> primes = new List<int>();
primes.Add(2);
for (int i = 1, found = 1; 2 * i + 1 <= limit && found < n; i++)
{
if (bits[i])
{
primes.Add(2 * i + 1);
found++;
}
}
return primes;
}
Para averiguar los primeros 100 números primos, se puede considerar el siguiente código Java.
int num = 2;
int i, count;
int nPrimeCount = 0;
int primeCount = 0;
do
{
for (i = 2; i <num; i++)
{
int n = num % i;
if (n == 0) {
nPrimeCount++;
// System.out.println(nPrimeCount + " " + "Non-Prime Number is: " + num);
num++;
break;
}
}
if (i == num) {
primeCount++;
System.out.println(primeCount + " " + "Prime number is: " + num);
num++;
}
}while (primeCount<100);
Para hacerlo más elegante, debe refactorizar su prueba IsPrime en un método separado, y manejar el bucle e incrementarlos fuera de eso.
Personalmente creo que esta es una implementación bastante corta y limpia (Java):
static ArrayList<Integer> getPrimes(int numPrimes) {
ArrayList<Integer> primes = new ArrayList<Integer>(numPrimes);
int n = 2;
while (primes.size() < numPrimes) {
while (!isPrime(n)) { n++; }
primes.add(n);
n++;
}
return primes;
}
static boolean isPrime(int n) {
if (n < 2) { return false; }
if (n == 2) { return true; }
if (n % 2 == 0) { return false; }
int d = 3;
while (d * d <= n) {
if (n % d == 0) { return false; }
d += 2;
}
return true;
}
Prueba este código
protected bool isPrimeNubmer(int n)
{
if (n % 2 == 0)
return false;
else
{
int j = 3;
int k = (n + 1) / 2 ;
while (j <= k)
{
if (n % j == 0)
return false;
j = j + 2;
}
return true;
}
}
protected void btn_primeNumbers_Click(object sender, EventArgs e)
{
string time = "";
lbl_message.Text = string.Empty;
int num;
StringBuilder builder = new StringBuilder();
builder.Append("<table><tr>");
if (int.TryParse(tb_number.Text, out num))
{
if (num < 0)
lbl_message.Text = "Please enter a number greater than or equal to 0.";
else
{
int count = 1;
int number = 0;
int cols = 11;
var watch = Stopwatch.StartNew();
while (count <= num)
{
if (isPrimeNubmer(number))
{
if (cols > 0)
{
builder.Append("<td>" + count + " - " + number + "</td>");
}
else
{
builder.Append("</tr><tr><td>" + count + " - " + number + "</td>");
cols = 11;
}
count++;
number++;
cols--;
}
else
number++;
}
builder.Append("</table>");
watch.Stop();
var elapsedms = watch.ElapsedMilliseconds;
double seconds = elapsedms / 1000;
time = seconds.ToString();
lbl_message.Text = builder.ToString();
lbl_time.Text = time;
}
}
else
lbl_message.Text = "Please enter a numberic number.";
lbl_time.Text = time;
tb_number.Text = "";
tb_number.Focus();
}
Here is the aspx code.
<form id="form1" runat="server">
<div>
<p>Please enter a number: <asp:TextBox ID="tb_number" runat="server"></asp:TextBox></p>
<p><asp:Button ID="btn_primeNumbers" runat="server" Text="Show Prime Numbers" OnClick="btn_primeNumbers_Click" />
</p>
<p><asp:Label ID="lbl_time" runat="server"></asp:Label></p>
<p><asp:Label ID="lbl_message" runat="server"></asp:Label></p>
</div>
</form>
Results: 10000 Prime Numbers in less than one second
100000 Prime Numbers in 63 seconds
Screenshot of first 100 Prime Numbers
Pruebe esta consulta LINQ, genera números primos como esperaba
var NoOfPrimes= 5;
var GeneratedPrime = Enumerable.Range(1, int.MaxValue)
.Where(x =>
{
return (x==1)? false:
!Enumerable.Range(1, (int)Math.Sqrt(x))
.Any(z => (x % z == 0 && x != z && z != 1));
}).Select(no => no).TakeWhile((val, idx) => idx <= NoOfPrimes-1).ToList();
Puedo ofrecer la siguiente solución de C #. De ninguna manera es rápido, pero es muy claro sobre lo que hace.
public static List<Int32> GetPrimes(Int32 limit)
{
List<Int32> primes = new List<Int32>() { 2 };
for (int n = 3; n <= limit; n += 2)
{
Int32 sqrt = (Int32)Math.Sqrt(n);
if (primes.TakeWhile(p => p <= sqrt).All(p => n % p != 0))
{
primes.Add(n);
}
}
return primes;
}
Olvidé los cheques, si el límite es negativo o es menor que dos (por el momento, el método al menos siempre devolverá dos como primo). Pero eso es todo fácil de arreglar.
ACTUALIZAR
Con los siguientes dos métodos de extensión
public static void Do<T>(this IEnumerable<T> collection, Action<T> action)
{
foreach (T item in collection)
{
action(item);
}
}
public static IEnumerable<Int32> Range(Int32 start, Int32 end, Int32 step)
{
for (int i = start; i < end; i += step)
}
yield return i;
}
}
puedes reescribirlo de la siguiente manera.
public static List<Int32> GetPrimes(Int32 limit)
{
List<Int32> primes = new List<Int32>() { 2 };
Range(3, limit, 2)
.Where(n => primes
.TakeWhile(p => p <= Math.Sqrt(n))
.All(p => n % p != 0))
.Do(n => primes.Add(n));
return primes;
}
Es menos eficiente (porque la raíz cuadrada es reevaluada con bastante frecuencia) pero es incluso un código más limpio. Es posible volver a escribir el código para enumerar perezosamente los números primos, pero esto desordenará bastante el código.
Resolviendo una vieja pregunta, pero me tropecé con ella mientras jugaba con LINQ.
Este código requiere .NET4.0 o .NET3.5 con extensiones paralelas
public List<int> GeneratePrimes(int n) {
var r = from i in Enumerable.Range(2, n - 1).AsParallel()
where Enumerable.Range(2, (int)Math.Sqrt(i)).All(j => i % j != 0)
select i;
return r.ToList();
}
Sé que pidió una solución que no sea de Haskell, pero la incluyo aquí en lo que se refiere a la pregunta, y también Haskell es hermoso para este tipo de cosas.
module Prime where
primes :: [Integer]
primes = 2:3:primes''
where
-- Every prime number other than 2 and 3 must be of the form 6k + 1 or
-- 6k + 5. Note we exclude 1 from the candidates and mark the next one as
-- prime (6*0+5 == 5) to start the recursion.
1:p:candidates = [6*k+r | k <- [0..], r <- [1,5]]
primes'' = p : filter isPrime candidates
isPrime n = all (not . divides n) $ takeWhile (/p -> p*p <= n) primes''
divides n p = n `mod` p == 0
Usando tu mismo algoritmo puedes hacerlo un poco más corto:
List<int> primes=new List<int>(new int[]{2,3});
for (int n = 5; primes.Count< numberToGenerate; n+=2)
{
bool isPrime = true;
foreach (int prime in primes)
{
if (n % prime == 0)
{
isPrime = false;
break;
}
}
if (isPrime)
primes.Add(n);
}
Use la estimación
pi(n) = n / log(n)
para el número de primos hasta n para encontrar un límite, y luego use un tamiz. La estimación subestima el número de primos hasta n algo, por lo que el tamiz será un poco más grande de lo necesario, lo cual está bien.
Este es mi tamiz Java estándar, calcula el primer millón de primos en aproximadamente un segundo en una computadora portátil normal:
public static BitSet computePrimes(int limit)
{
final BitSet primes = new BitSet();
primes.set(0, false);
primes.set(1, false);
primes.set(2, limit, true);
for (int i = 0; i * i < limit; i++)
{
if (primes.get(i))
{
for (int j = i * i; j < limit; j += i)
{
primes.clear(j);
}
}
}
return primes;
}
Use un generador de números primos para crear primes.txt y luego:
class Program
{
static void Main(string[] args)
{
using (StreamReader reader = new StreamReader("primes.txt"))
{
foreach (var prime in GetPrimes(10, reader))
{
Console.WriteLine(prime);
}
}
}
public static IEnumerable<short> GetPrimes(short upTo, StreamReader reader)
{
int count = 0;
string line = string.Empty;
while ((line = reader.ReadLine()) != null && count++ < upTo)
{
yield return short.Parse(line);
}
}
}
En este caso, uso Int16 en la firma del método, por lo que mi archivo primes.txt contiene números del 0 al 32767. Si desea extender esto a Int32 o Int64, su primes.txt podría ser significativamente más grande.
Utilizando la programación basada en flujo en Java funcional , se me ocurrió lo siguiente. El tipo Natural es esencialmente un BigInteger > = 0.
public static Stream<Natural> sieve(final Stream<Natural> xs)
{ return cons(xs.head(), new P1<Stream<Natural>>()
{ public Stream<Natural> _1()
{ return sieve(xs.tail()._1()
.filter($(naturalOrd.equal().eq(ZERO))
.o(mod.f(xs.head())))); }}); }
public static final Stream<Natural> primes
= sieve(forever(naturalEnumerator, natural(2).some()));
Ahora tiene un valor que puede transportar, que es una corriente infinita de primos. Puedes hacer cosas como esta:
// Take the first n primes
Stream<Natural> nprimes = primes.take(n);
// Get the millionth prime
Natural mprime = primes.index(1000000);
// Get all primes less than n
Stream<Natural> pltn = primes.takeWhile(naturalOrd.lessThan(n));
Una explicación del tamiz:
- Suponga que el primer número en la secuencia de argumento es primo y póngalo al frente de la secuencia de retorno. El resto de la secuencia de retorno es un cálculo que se producirá solo cuando se solicite.
- Si alguien pregunta por el resto de la transmisión, llame al tamiz sobre el resto de la secuencia de la discusión, filtrando los números divisibles por el primer número (el resto de la división es cero).
Necesita tener las siguientes importaciones:
import fj.P1;
import static fj.FW.$;
import static fj.data.Enumerator.naturalEnumerator;
import fj.data.Natural;
import static fj.data.Natural.*;
import fj.data.Stream;
import static fj.data.Stream.*;
import static fj.pre.Ord.naturalOrd;
// Create a test range
IEnumerable<int> range = Enumerable.Range(3, 50 - 3);
// Sequential prime number generator
var primes_ = from n in range
let w = (int)Math.Sqrt(n)
where Enumerable.Range(2, w).All((i) => n % i > 0)
select n;
// Note sequence of output:
// 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,
foreach (var p in primes_)
Trace.Write(p + ", ");
Trace.WriteLine("");