La manera más elegante de generar números primos

¿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 BigInteger s de Java y nextProbablePrime para 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).

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

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 GeneratePrimesNaive(int n) { List primes = new List(); 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 GeneratePrimesSieveOfEratosthenes(int n) { int limit = ApproximateNthPrime(n); BitArray bits = SieveOfEratosthenes(limit); List primes = new List(); 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 GeneratePrimesSieveOfSundaram(int n) { int limit = ApproximateNthPrime(n); BitArray bits = SieveOfSundaram(limit); List primes = new List(); 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; } 

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

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

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, Iterable { 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 iterator() { return this; } } @Test public void printPrimes() { for (BigInteger p : new PrimeGenerator()) { System.out.println(p); } } 

De ninguna manera eficiente, pero tal vez la más legible:

 public static IEnumerable GeneratePrimes() { return Range(2).Where(candidate => Range(2, (int)Math.Sqrt(candidate))) .All(divisor => candidate % divisor != 0)); } 

con:

 public static IEnumerable 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.

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 np = n `mod` p == 0 

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

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 GetPrimes(Int32 limit) { List primes = new List() { 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(this IEnumerable collection, Action action) { foreach (T item in collection) { action(item); } } public static IEnumerable 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 GetPrimes(Int32 limit) { List primes = new List() { 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.

Aquí hay una implementación de Sieve of Eratosthenes en C #:

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

Usando tu mismo algoritmo puedes hacerlo un poco más corto:

 List primes=new List(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); } 

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 Primes(int count) { return Primes().Take(count); } static IEnumerable Primes() { List cache = new List(); 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 Primes() { yield return 2; List cache = new List() { 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; } } 

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) 

Para hacerlo más elegante, debe refactorizar su prueba IsPrime en un método separado, y manejar el bucle e incrementarlos fuera de eso.

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 numbers = new Range(1, 100); Iterable primes = numbers.inject(numbers, new Functions.Injecter, Integer>() { public Iterable call(Iterable 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() { public Boolean call(Integer n) throws Exception { return n > number && n % number == 0; } }); } }); 

Aquí hay un ejemplo de código python que imprime la sum 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 

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.

Utilizando la progtwigción basada en flujo en Java funcional , se me ocurrió lo siguiente. El tipo Natural es esencialmente un BigInteger > = 0.

 public static Stream sieve(final Stream xs) { return cons(xs.head(), new P1>() { public Stream _1() { return sieve(xs.tail()._1() .filter($(naturalOrd.equal().eq(ZERO)) .o(mod.f(xs.head())))); }}); } public static final Stream primes = sieve(forever(naturalEnumerator, natural(2).some())); 

Ahora tiene un valor que puede transportar, que es una stream infinita de primos. Puedes hacer cosas como esta:

 // Take the first n primes Stream nprimes = primes.take(n); // Get the millionth prime Natural mprime = primes.index(1000000); // Get all primes less than n Stream pltn = primes.takeWhile(naturalOrd.lessThan(n)); 

Una explicación del tamiz:

  1. Suponga que el primer número en la secuencia de argumento es primo y póngalo al frente de la secuencia de retorno. El rest de la secuencia de retorno es un cálculo que se producirá solo cuando se solicite.
  2. Si alguien pregunta por el rest de la transmisión, llame al tamiz sobre el rest de la secuencia de la discusión, filtrando los números divisibles por el primer número (el rest 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; 

Personalmente creo que esta es una implementación bastante corta y limpia (Java):

 static ArrayList getPrimes(int numPrimes) { ArrayList primes = new ArrayList(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; } 

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(); 
 // Create a test range IEnumerable 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(""); 

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; 

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  

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 comstackción, encoding muy densa estilo + Ni siquiera hice el primer bash 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 comstackció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 { // Integer HOW_MANY; HashSethashSet=new HashSet(); 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 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 resultSet=new HashSet(); // 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 

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(""); 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(""); } else { builder.Append(""); cols = 11; } count++; number++; cols--; } else number++; } builder.Append("
" + count + " - " + number + "
" + count + " - " + number + "
"); 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.

 

Please enter a number:

Results: 10000 Prime Numbers in less than one second

100000 Prime Numbers in 63 seconds

Screenshot of first 100 Prime Numbers enter image description here