Manière la plus élégante de générer des nombres premiers

Quelle est la manière la plus élégante de mettre en œuvre cette fonction:

ArrayList generatePrimes(int n) 

Cette fonction génère les premiers n primes (edit: où n>1 ), donc generatePrimes(5) renverra une ArrayList avec {2, 3, 5, 7, 11} . (Je le fais en C #, mais je suis satisfait d’une implémentation Java – ou de tout autre langage similaire (donc pas Haskell)).

Je sais comment écrire cette fonction, mais quand je l’ai fait hier soir, ça n’a pas été aussi bon que je l’espérais. Voici ce que j’ai imaginé:

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

Je ne suis pas trop préoccupé par la vitesse, même si je ne veux pas que ce soit manifestement inefficace. Peu importe la méthode utilisée (naïf, tamis ou autre), mais je veux que ce soit assez court et évident.

Edit : Merci à tous ceux qui ont répondu, même si beaucoup n’ont pas répondu à ma question. Pour réitérer, je voulais un beau morceau de code propre qui a généré une liste de nombres premiers. Je sais déjà comment le faire de différentes manières, mais je suis enclin à écrire du code qui n’est pas aussi clair que cela pourrait l’être. Dans ce fil, quelques bonnes options ont été proposées:

  • Une meilleure version de ce que j’avais à l’origine (Peter Smit, jmservera et Rekreativc)
  • Une mise en place très propre du tamis d’Eratosthenes (starblue)
  • Utilisez Java BigInteger s et nextProbablePrime pour un code très simple, même si je ne peux pas imaginer qu’il soit particulièrement efficace (dfa)
  • Utilisez LINQ pour générer paresseusement la liste des nombres premiers (Maghis)
  • Mettez beaucoup de nombres premiers dans un fichier texte et lisez-les si nécessaire (darin)

Edit 2 : J’ai implémenté en C # quelques méthodes données ici et une autre méthode non mentionnée ici. Ils trouvent tous les premiers n premiers efficacement (et j’ai une méthode décente pour trouver la limite à fournir aux tamis).

Utiliser le devis

 pi(n) = n / log(n) 

pour le nombre de nombres premiers jusqu’à n pour trouver une limite, puis utilisez un tamis. L’estimation sous-estime le nombre de nombres premiers jusqu’à n, de sorte que le tamis sera légèrement plus grand que nécessaire, ce qui est correct.

Ceci est mon tamis Java standard, calcule le premier million de nombres premiers en environ une seconde sur un ordinateur portable 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; } 

Un grand merci à tous ceux qui ont donné des réponses utiles. Voici mes implémentations de quelques méthodes différentes pour trouver les premiers n nombres premiers en C #. Les deux premières méthodes sont à peu près ce qui a été posté ici. (Les noms des affiches sont à côté du titre.) Je prévois de faire le tamis d’Atkin parfois, même si je pense que ce ne sera pas aussi simple que les méthodes actuelles. Si quelqu’un peut voir un moyen d’améliorer l’une de ces méthodes, j’aimerais savoir 🙂

Méthode standard ( Peter Smit , jmservera , Rekreativc )

Le premier nombre premier est 2. Ajoutez ceci à une liste de nombres premiers. Le nombre premier suivant est le prochain chiffre qui n’est pas divisible par aucun nombre de cette liste.

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

Cela a été optimisé en ne testant que la divisibilité jusqu'à la racine carrée du nombre testé; et en ne testant que des nombres impairs. Cela peut être encore optimisé en testant uniquement des nombres de la forme 6k+[1, 5] ou 30k+[1, 7, 11, 13, 17, 19, 23, 29] ou ainsi de suite .

Tamis d'Eratosthenes ( Starblue )

Cela trouve tous les nombres premiers à k . Pour faire une liste des n premiers nombres premiers, nous devons d'abord approcher la valeur du n- ième prime. La méthode suivante, décrite ici , le fait.

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

Tamis de Sundaram

Je n'ai découvert ce tamis que récemment, mais il peut être implémenté simplement. Mon implémentation n'est pas aussi rapide que le tamis d'Eratosthène, mais elle est nettement plus rapide que la méthode naïve.

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

Ressusciter une vieille question, mais je suis tombé dessus en jouant avec LINQ.

Ce code nécessite .NET4.0 ou .NET3.5 avec des extensions parallèles

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

Vous êtes sur la bonne voie.

Certains commentaires

  • primes.Add (3); fait que cette fonction ne fonctionne pas pour nombre = 1

  • Vous n’avez pas à tester la division avec des nombres plus grands que la racine carrée du nombre à tester.

Code suggéré:

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

Vous devriez jeter un coup d’oeil aux nombres premiers probables . En particulier, examinez les algorithmes randomisés et le test de primalité de Miller – Rabin .

Par souci d’exhaustivité, vous pouvez simplement utiliser 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); } } 

En aucun cas efficace, mais peut-être le plus lisible:

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

avec:

 public static IEnumerable Range(int from, int to = int.MaxValue) { for (int i = from; i <= to; i++) yield return i; } 

En fait, juste une variation de certains articles ici avec un formatage plus agréable.

Je sais que vous avez demandé une solution non-Haskell, mais je l’inclus ici car cela concerne la question et Haskell est également magnifique pour ce genre de chose.

 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 

Utilisez un générateur de nombres premiers pour créer primes.txt, puis:

 class Program { static void Main(ssortingng[] 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; ssortingng line = ssortingng.Empty; while ((line = reader.ReadLine()) != null && count++ < upTo) { yield return short.Parse(line); } } } 

Dans ce cas, j'utilise Int16 dans la signature de la méthode, donc mon fichier primes.txt contient des nombres de 0 à 32767. Si vous souhaitez l'étendre à Int32 ou Int64, votre primes.txt pourrait être considérablement plus grand.

Je peux offrir la solution C # suivante. Ce n’est pas rapide, mais il est très clair sur ce qu’il fait.

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

J’ai omis tout contrôle – si la limite est négative ou inférieure à deux (pour le moment, la méthode restra au moins deux en prime). Mais tout est facile à corriger.

METTRE À JOUR

Avec les deux méthodes d’extension suivantes

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

vous pouvez le réécrire comme suit.

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

C'est moins efficace (car la racine carrée est réévaluée assez souvent) mais c'est un code encore plus propre. Il est possible de réécrire le code pour énumérer paresseusement les nombres premiers, mais cela encombrera un peu le code.

Voici une implémentation 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 } 

En utilisant votre même algorithme, vous pouvez le faire un peu plus court:

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

J’ai écrit une implémentation Eratosthenes simple en c # en utilisant un LINQ.

Malheureusement, LINQ ne fournit pas une séquence infinie d’ints, vous devez donc utiliser int.MaxValue 🙁

J’ai dû mettre en cache dans un type anonyme le candidat sqrt pour éviter de le calculer pour chaque prime en cache (un peu moche).

J’utilise une liste de nombres premiers précédents jusqu’à sqrt du candidat

 cache.TakeWhile(c => c <= candidate.Sqrt) 

et vérifier chaque Int à partir de 2 contre

 .Any(cachedPrime => candidate.Current % cachedPrime == 0) 

Voici le code:

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

Une autre optimisation est d'éviter de vérifier les nombres pairs et de ne retourner que 2 avant de créer la liste. De cette façon, si la méthode d'appel demande simplement 1 prime, cela évitera tout le désordre:

 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 by St.Wittum 13189 Berlin ALLEMAGNE sous licence CC-BY-SA https://creativecommons.org/licenses/by-sa/3.0/

La manière simple mais la plus élégante de calculer ALL PRIMES serait la suivante, mais cette méthode est lente et les coûts de mémoire sont beaucoup plus élevés pour les nombres plus élevés, car la fonction faculté (!) Montre une variation de Wilson Theoreme dans une application. générer tous les nombres premiers par algorithme implémenté 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) 

Pour le rendre plus élégant, vous devez réorganiser votre test IsPrime dans une méthode distincte et gérer le bouclage et les incréments en dehors de cela.

Je l’ai fait en Java en utilisant une bibliothèque fonctionnelle que j’ai écrite, mais comme ma bibliothèque utilise les mêmes concepts que les énumérations, je suis sûr que le code est 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; } }); } }); 

Voici un exemple de code python qui affiche la sum de tous les nombres premiers sous deux millions:

 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 

C’est le plus élégant que je puisse imaginer à court préavis.

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

J'espère que cela vous aidera à vous faire une idée. Je suis sûr que cela peut être optimisé, mais cela devrait vous donner une idée de la façon dont votre version pourrait être rendue plus élégante.

EDIT: Comme indiqué dans les commentaires, cet algorithme renvoie en effet des valeurs erronées pour numberToGenerate <2. Je veux juste souligner que je n'essayais pas de lui poster une méthode géniale pour générer des nombres premiers (regardez la réponse d'Henri pour cela), J'étais en train de me rappeler comment sa méthode pouvait être rendue plus élégante.

En utilisant la programmation basée sur les stream dans Java fonctionnel , j’ai trouvé ce qui suit. Le type Natural est essentiellement 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())); 

Maintenant, vous avez une valeur, que vous pouvez transporter, qui est un stream infini de nombres premiers. Vous pouvez faire des choses comme ceci:

 // 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)); 

Une explication du tamis:

  1. Supposons que le premier nombre du stream d’arguments est premier et le place au début du stream de retour. Le rest du stream de retour est un calcul à produire uniquement lorsque demandé.
  2. Si quelqu’un demande le rest du stream, appelez sieve sur le rest du stream d’arguments, en filtrant les nombres divisibles par le premier nombre (le rest de la division est égal à zéro).

Vous devez avoir les importations suivantes:

 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; 

Personnellement, je pense que c’est une implémentation courte et propre (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; } 

Essayez cette requête LINQ, elle génère des nombres premiers comme prévu

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

La méthode la plus simple est l’essai et l’erreur: vous essayez si un nombre compris entre 2 et n-1 divise votre nombre premier de candidats n.
Les premiers raccourcis sont bien sûr a) il suffit de vérifier les nombres impairs, et b) il suffit de vérifier les diviseurs jusqu’à sqrt (n).

Dans votre cas, où vous générez également tous les nombres premiers précédents dans le processus, il vous suffit de vérifier si l’un des nombres premiers de votre liste, jusqu’à sqrt (n), divise n.
Devrait être le plus rapide possible pour votre argent 🙂

modifier
Ok, code, vous l’avez demandé. Mais je vous préviens :-), ceci est un code Delphi rapide et sale de 5 minutes:

 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; 

Pour connaître les 100 premiers nombres premiers, le code Java suivant peut être considéré.

 int num = 2; int i, count; int nPrimeCount = 0; int primeCount = 0; do { for (i = 2; i  

Je l’ai eu en première lecture de “Sieve of Atkin” sur Wikki, plus une reflection préalable – j’ai passé beaucoup de temps à coder à partir de zéro et à être complètement mis à zéro sur les critiques de mon compilateur style + Je n’ai même pas fait une première tentative pour exécuter le code… beaucoup de paradigmes que j’ai appris à utiliser sont là, lisez et pleurez, obtenez ce que vous pouvez.

Soyez absolument sûr de tester tout cela avant toute utilisation, ne le présentez certainement à personne – c’est pour lire et considérer les idées. Je dois utiliser l’outil de primalité, c’est là que je commence chaque fois que je dois faire quelque chose.

Obtenez une compilation propre, puis commencez à enlever ce qui est défectueux – j’ai près de 108 millions de frappes de code utilisable qui le font de cette façon, … utilisez ce que vous pouvez.

Je travaillerai sur ma version demain.

 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.Ssortingng LINE_SEPARATOR = new java.lang.Ssortingng(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.Ssortingng[] args) { return; } } //eof 

Essayez ce code.

 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.ToSsortingng(); lbl_message.Text = builder.ToSsortingng(); 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 entrer la description de l'image ici