Il modo più elegante per generare numeri primi [chiuso]
https://stackoverflow.com/questions/1042902
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Qual è il modo più elegante per implementare questa funzione:
ArrayList generatePrimes(int n)
Questa funzione genera i primi n numeri primi (modifica: dove n>1), quindi generatePrimes(5) restituirà un ArrayList con {2, 3, 5, 7, 11}. (Lo sto facendo in C #, ma sono contento di un'implementazione Java - o di qualsiasi altro linguaggio simile per quella materia (quindi non Haskell)).
So come scrivere questa funzione, ma quando l'ho fatto ieri sera non è andata bene come speravo. Ecco cosa mi è venuto in mente:
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;
}
Non sono troppo preoccupato per la velocità, anche se non voglio che sia ovviamente inefficiente. Non mi importa quale metodo viene utilizzato (ingenuo o setaccio o altro), ma voglio che sia abbastanza breve e ovvio come funziona.
Modifica : grazie a tutti coloro che hanno risposto, sebbene molti non abbiano risposto alla mia vera domanda. Per ribadire, volevo un bel pezzo di codice pulito che generasse un elenco di numeri primi. So già come farlo in diversi modi, ma sono incline a scrivere codice che non sia così chiaro come potrebbe essere. In questa discussione sono state proposte alcune buone opzioni:
- Una versione migliore di quello che avevo in origine (Peter Smit, jmservera e Rekreativc)
- Un'implementazione molto pulita del setaccio di Eratosthenes (starblue)
- Usa Java
BigIntegersenextProbablePrimeper un codice molto semplice, anche se non riesco a immaginare che sia particolarmente efficiente (dfa) - Usa LINQ per generare pigramente l'elenco dei numeri primi (Maghis)
- Metti molti numeri primi in un file di testo e leggili quando necessario (darin)
Modifica 2 : ho implementato in C # un paio dei metodi indicati qui e un altro metodo non menzionato qui. Trovano tutti i primi n primi in modo efficace (e ho un metodo decente per trovare il limite da fornire ai setacci).
Soluzione 2
Mille grazie a tutti coloro che hanno dato risposte utili. Ecco le mie implementazioni di alcuni metodi diversi per trovare i primi n primi in C #. I primi due metodi sono praticamente ciò che è stato pubblicato qui. (I nomi dei poster sono accanto al titolo.) Ho intenzione di fare il setaccio di Atkin qualche volta, anche se sospetto che non sarà così semplice come i metodi qui attualmente. Se qualcuno può vedere un modo per migliorare uno di questi metodi, mi piacerebbe sapere :-)
Metodo standard ( Peter Smit , jmservera , Rekreativc )
Il primo numero primo è 2. Aggiungi questo a un elenco di numeri primi. Il primo primo è il numero successivo che non è equamente divisibile per nessun numero in questo elenco.
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;
}
Questo è stato ottimizzato testando solo la divisibilità fino alla radice quadrata del numero da testare; e testando solo numeri dispari. Questo può essere ulteriormente ottimizzato testando solo i numeri del modulo 6k+[1, 5], oppure 30k+[1, 7, 11, 13, 17, 19, 23, 29] o così su .
Sieve of Eratosthenes ( starblue )
Questo trova tutti i numeri primi in k . Per fare un elenco dei primi n primi, dobbiamo prima approssimare il valore del n primo. Il seguente metodo, come descritto qui , fa questo.
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;
}
Sieve of Sundaram
Ho scoperto questo setaccio di recente, ma può essere implementato in modo abbastanza semplice. La mia implementazione non è rapida come il setaccio di Eratostene, ma è significativamente più veloce del metodo 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;
}
Altri suggerimenti
Utilizza il preventivo
pi(n) = n / log(n)
per il numero di numeri primi fino a n per trovare un limite, quindi utilizzare un setaccio. La stima sottostima il numero di numeri primi fino a n un po ', quindi il setaccio sarà leggermente più grande del necessario, il che è ok.
Questo è il mio setaccio Java standard, calcola il primo milione di numeri primi in circa un secondo su un normale laptop:
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;
}
Riprendendo una vecchia domanda, ma mi sono imbattuto in esso mentre giocavo con LINQ.
Questo codice richiede .NET4.0 o .NET3.5 con estensioni parallele
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();
}
Sei sulla buona strada.
Alcuni commenti
-
primes.Add (3); fa in modo che questa funzione non funzioni per numero = 1
-
Non devi testare la divisione con primenumbers più grandi dello squareroot del numero da testare.
Codice suggerito:
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;
}
dovresti dare un'occhiata a numeri primi probabili . In particolare dai un'occhiata a Algoritmi randomizzati e Miller & # 8211; Test di primalità di Rabin .
Per completezza potresti semplicemente usare 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);
}
}
In nessun modo efficace, ma forse il più leggibile:
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;
}
In effetti solo una variante di alcuni post qui con una formattazione migliore.
So che hai chiesto una soluzione non Haskell, ma la includo qui per quanto riguarda la domanda e anche Haskell è bello per questo tipo di cose.
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
Usa un generatore di numeri per creare primes.txt e quindi:
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);
}
}
}
In questo caso uso Int16 nella firma del metodo, quindi il mio file primes.txt contiene numeri da 0 a 32767. Se vuoi estenderlo a Int32 o Int64 il tuo primes.txt potrebbe essere significativamente più grande.
Posso offrire la seguente soluzione C #. Non è affatto veloce, ma è molto chiaro su ciò che fa.
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;
}
Ho lasciato fuori qualsiasi controllo - se il limite è negativo o minore di due (per il momento il metodo restituirà almeno due come primo). Ma è tutto facile da risolvere.
Aggiorna
Con i seguenti due metodi di estensione
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;
}
}
puoi riscriverlo come segue.
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;
}
È meno efficiente (perché la radice quadrata viene rivalutata abbastanza spesso) ma è anche un codice più pulito. È possibile riscrivere il codice per enumerare pigramente i numeri primi, ma ciò ingombra un po 'il codice.
Ecco un'implementazione di Sieve of Eratosthenes in 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 di St.Wittum 13189 Berlin GERMANIA sotto licenza CC-BY-SA https://creativecommons.org/licenses/by-sa/3.0/
Il modo più semplice ma elegante per calcolare TUTTI I PRIMI sarebbe questo, ma in questo modo è lento e i costi di memoria sono molto più alti per numeri più alti perché usando la funzione di facoltà (!) ... ma dimostra una variazione di Wilson Theoreme in un'applicazione per generare tutti i numeri primi dall'algoritmo implementato in 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 il tuo stesso algoritmo puoi farlo un po 'più breve:
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);
}
Ho scritto una semplice implementazione di Eratosthenes in c # usando alcuni LINQ.
Sfortunatamente LINQ non fornisce una sequenza infinita di ints quindi devi usare int.MaxValue :(
Ho dovuto memorizzare nella cache in un tipo anonimo il candidato sqrt per evitare di calcolarlo per ogni primo memorizzato nella cache (sembra un po 'brutto).
Uso un elenco di numeri primi precedenti fino a sqrt del candidato
cache.TakeWhile(c => c <= candidate.Sqrt)
e controlla ogni Int a partire da 2 contro di esso
.Any(cachedPrime => candidate.Current % cachedPrime == 0)
Ecco il codice:
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;
}
}
Un'altra ottimizzazione è quella di evitare di controllare i numeri pari e restituire solo 2 prima di creare l'elenco. In questo modo se il metodo di chiamata richiede solo 1 primo eviterà tutto il casino:
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;
}
}
Per renderlo più elegante, dovresti trasformare il tuo test IsPrime in un metodo separato e gestire il loop e gli incrementi al di fuori di questo.
L'ho fatto in Java usando una libreria funzionale che ho scritto, ma poiché la mia libreria usa gli stessi concetti delle enumerazioni, sono sicuro che il codice sia adattabile:
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;
}
});
}
});
Ecco un esempio di codice Python che stampa la somma di tutti i numeri primi sotto i due milioni:
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
Questo è il più elegante che mi viene in mente in breve tempo.
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;
}
Spero che questo ti aiuti a darti un'idea. Sono sicuro che questo può essere ottimizzato, tuttavia dovrebbe darti un'idea di come la tua versione potrebbe essere resa più elegante.
EDIT: Come notato nei commenti questo algoritmo restituisce davvero valori errati per numberToGenerate < 2. Voglio solo sottolineare che non stavo provando a pubblicarlo come un ottimo metodo per generare numeri primi (guarda la risposta di Henri per questo), stavo sottolineando allegramente come il suo metodo potesse essere reso più elegante.
Utilizzando la programmazione basata su stream in Java funzionale , ho trovato quanto segue. Il tipo Natural è essenzialmente 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()));
Ora hai un valore, che puoi portare in giro, che è un flusso infinito di numeri primi. Puoi fare cose del genere:
// 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 spiegazione del setaccio:
- Supponi che il primo numero nel flusso di argomenti sia primo e mettilo all'inizio del flusso di ritorno. Il resto del flusso di ritorno è un calcolo da produrre solo quando richiesto.
- Se qualcuno chiede il resto dello stream, chiama sieve sul resto dello stream degli argomenti, filtrando i numeri divisibili per il primo numero (il resto della divisione è zero).
Devi avere le seguenti importazioni:
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 penso che questo sia un amplificatore & piuttosto breve; implementazione pulita (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;
}
Prova questa query LINQ, genera numeri primi come previsto
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("");
Il metodo più semplice è la prova e l'errore: provi se un numero compreso tra 2 e n-1 divide il numero primo candidato.
Le prime scorciatoie sono ovviamente a) devi solo controllare i numeri dispari eb) devi solo verificare la presenza di divisori fino a sqrt (n).
Nel tuo caso, in cui generi anche tutti i numeri primi precedenti nel processo, devi solo verificare se uno dei numeri primi nel tuo elenco, fino a sqrt (n), divide n.
Dovrebbe essere il più veloce che puoi ottenere per i tuoi soldi :-)
modifica
Ok, codice, l'hai chiesto. Ma ti avverto :-), questo è il codice Delphi veloce e sporco di 5 minuti:
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;
Per scoprire i primi 100 numeri primi, può essere considerato il seguente codice 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);
Ho ottenuto questo dalla prima lettura di " Sieve of Atkin " su Wikki e qualche altro pensiero precedente che ho pensato a questo: passo molto tempo a scrivere codice da zero e mi azzeramento completamente perché le persone sono critiche nei confronti del mio stile di compilazione, molto denso, e non ho nemmeno fatto un primo tentativo di esecuzione il codice ... molti dei paradigmi che ho imparato a usare sono qui, basta leggere e piangere, ottenere ciò che puoi.
Sii assolutamente & amp; assolutamente sicuro di provare davvero tutto questo prima di ogni utilizzo, di sicuro non mostrarlo a nessuno - è per leggere e considerare le idee. Devo far funzionare lo strumento di primalità, quindi è qui che inizio ogni volta che devo far funzionare qualcosa.
Ottieni una compilazione pulita, quindi inizia a rimuovere ciò che è difettoso: ho quasi 108 milioni di battute di codice utilizzabile che lo fanno in questo modo, ... usa quello che puoi.
Domani lavorerò sulla mia versione.
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
Prova questo codice.
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();
}
Ecco il codice 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>
Risultati: 10000 numeri primi in meno di un secondo
100000 numeri primi in 63 secondi
Schermata dei primi 100 numeri primi
