La forma más elegante de generar números primos [cerrado]
https://stackoverflow.com/questions/1042902
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
¿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 (editar: donde n>1), por lo que generatePrimes(5) devolverá un 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 el caso (así que no Haskell)).
Sé cómo escribir esta función, pero cuando lo hice anoche no terminó tan bien como esperaba. Esto 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 muchas maneras diferentes, 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 agradable de lo que tenía originalmente (Peter Smit, jmservera y Rekreativc)
- Una implementación muy limpia del tamiz de Eratóstenes (starblue)
- Use
BigIntegersynextProbablePrimede Java para un código muy simple, aunque no puedo imaginar que sea particularmente eficiente (dfa) - Use LINQ para generar perezosamente la lista de primos (Maghis)
- Ponga muchos números primos en un archivo de texto y léalos cuando sea necesario (cariño)
Editar 2 : Tengo implementó en C # algunos de los métodos dados aquí, y otro método no mencionado aquí. Todos encuentran los primeros primos n de manera efectiva (y tengo un método decente de encontrar el límite para proporcionar a los tamices).
Solución 2
Muchas gracias a todos los que dieron respuestas útiles. Aquí están mis implementaciones de algunos métodos diferentes para encontrar los primeros primos n en C #. Los dos primeros 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 alguno 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 primos. El siguiente número primo es el siguiente número que no es divisible 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 probando solo la divisibilidad hasta la raíz cuadrada del número que se está probando; y solo probando números impares. Esto se puede optimizar aún más probando solo los números de la forma 6k+[1, 5], o 30k+[1, 7, 11, 13, 17, 19, 23, 29] o así en .
Tamiz de Eratóstenes ( starblue )
Esto encuentra todos los primos para k . Para hacer una lista de los primeros primos n , primero necesitamos aproximar el valor del primo n . 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
Solo descubrí este tamiz recientemente, pero puede implementarse de manera bastante simple. 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;
}
Otros consejos
Usa la estimación
pi(n) = n / log(n)
para el número de primos hasta n para encontrar un límite, y luego usar un tamiz. La estimación subestima el número de primos hasta n, 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;
}
Resucitando una vieja pregunta, pero me topé 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();
}
Estás en el buen camino.
Algunos comentarios
-
primos. Añadir (3); hace que esta función no funcione para number = 1
-
No tiene que probar la división con números primos 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 echar un vistazo a primos probables . En particular, eche un vistazo a Algoritmos aleatorios y Miller & # 8211; Prueba de primalidad Rabin .
En aras de la integridad, puede utilizar 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);
}
}
De ninguna manera eficiente, pero quizás el 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 agradable.
Sé que solicitó una solución que no sea de Haskell, pero la incluyo aquí en relación con la pregunta y también Haskell es hermosa 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
Utilice un generador de números 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 mayor.
Puedo ofrecer la siguiente solución de C #. De ninguna manera es rápido, pero es muy claro acerca de 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;
}
Omití cualquier verificación, si el límite es negativo o menor que dos (por el momento, el método siempre devolverá al menos dos como primo). Pero todo eso es fácil de arreglar.
UPDATE
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;
}
}
puede 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 se reevalúa con bastante frecuencia) pero es un código aún más limpio. Es posible reescribir el código para enumerar perezosamente los números primos, pero esto saturará bastante el código.
Aquí hay una implementación de Tamiz de Eratóstenes 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
}
Derechos de autor 2009 por St.Wittum 13189 Berlín ALEMANIA bajo licencia CC-BY-SA https://creativecommons.org/licenses/by-sa/3.0/
La forma simple pero más elegante de calcular TODAS LAS PRIMAS sería esta, pero de esta manera es lento y los costos de memoria son mucho más altos para números más altos porque usando la función facultad (!) ... pero demuestra una variación del teorema de Wilson en una aplicación para generar todos los números 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)
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);
}
Escribí una implementación simple de Eratóstenes en C # usando algo de LINQ.
Desafortunadamente LINQ no proporciona una secuencia infinita de entradas, por lo que debe usar int.MaxValue :(
Tuve que almacenar en caché en un tipo anónimo el sqrt candidato para evitar calcularlo para cada primo en caché (se ve un poco feo).
Uso una lista de números primos anteriores hasta sqrt del candidato
cache.TakeWhile(c => c <= candidate.Sqrt)
y verifique cada Int a partir de 2 contra él
.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 verificar números pares y devolver solo 2 antes de crear la Lista. De esta manera, si el método de llamada solo pide 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;
}
}
Para hacerlo más elegante, debe refactorizar su prueba IsPrime en un método separado y manejar los bucles e incrementos fuera de eso.
Lo hice en Java usando una biblioteca funcional que escribí, pero como mi biblioteca usa los mismos conceptos que Enumeraciones, 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;
}
});
}
});
Aquí hay un ejemplo de código de Python que imprime la suma de todos los números 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
Esto es lo más elegante que se me ocurre a corto plazo.
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 te 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 publicarle un gran método para generar números primos (mira la respuesta de Henri para eso), estaba señalando apenas cómo su método podría hacerse más elegante.
Utilizando la programación basada en secuencias en Java funcional , se me ocurrió lo siguiente. El tipo Natural es esencialmente un BigInteger & Gt; = 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 tienes un valor que puedes llevar, que es un flujo infinito de números 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 argumentos 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 secuencia, llame al tamiz en el resto de la secuencia de argumentos, filtrando los números divisibles por el primer número (el resto de la división es cero).
Debe 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 este es un amplificador & bastante corto; implementación 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;
}
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<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("");
El método más simple es la prueba y el error: intenta si algún número entre 2 y n-1 divide a tu candidato primo n.
Los primeros atajos son, por supuesto, a) solo tiene que verificar los números impares, yb) solo tiene que verificar los divisores hasta sqrt (n).
En su caso, donde también genera todos los primos anteriores en el proceso, solo tiene que verificar si alguno de los primos en su lista, hasta sqrt (n), divide n.
Debería ser lo más rápido que pueda obtener por su dinero :-)
editar
Ok, código, lo pediste. Pero te advierto :-), este es un código de Delphi rápido y sucio de 5 minutos:
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, puede considerarse 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);
Obtuve esto por primera lectura de " Sieve of Atkin " en Wikki más alguna reflexión previa que le he dado a esto: paso mucho tiempo codificando desde cero y me pongo completamente a cero en las personas que critican mi estilo de codificación muy denso como el compilador + Ni siquiera he hecho un 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.
Sea absolutamente & amp; totalmente seguro de probar todo esto antes de cualquier uso, seguro que no se lo muestres a nadie: es para leer y considerar las ideas. Necesito que funcione la herramienta de primalidad, así que aquí es donde empiezo cada vez que tengo que hacer que algo funcione.
Obtenga una compilación limpia, luego comience a quitar lo que es defectuoso: tengo casi 108 millones de pulsaciones de teclas de código utilizable 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
Pruebe 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();
}
Aquí está el código aspx.
<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>
Resultados: 10000 números primos en menos de un segundo
100000 números primos en 63 segundos
Captura de pantalla de los primeros 100 números primos
