Le moyen le plus élégant de générer des nombres premiers [fermé]
https://stackoverflow.com/questions/1042902
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Quel est le moyen le plus élégant d'implémenter cette fonction:
ArrayList generatePrimes(int n)
Cette fonction génère les premiers n nombres premiers (modifier: où n>1). Ainsi, generatePrimes(5) renverra un ArrayList avec {2, 3, 5, 7, 11}. (Je le fais en C #, mais je suis satisfait d’une implémentation de Java - ou de tout autre langage similaire (donc pas Haskell)).
Je sais comment écrire cette fonction, mais quand je l’ai faite la nuit dernière, elle n’a pas été aussi belle que je l’espérais. Voici ce que je suis venu avec:
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;
}
La vitesse ne me préoccupe pas trop, même si je ne veux pas que ce soit manifestement inefficace. Je ne me soucie pas de la méthode utilisée (naïve ou tamis ou quoi que ce soit d'autre), mais je veux qu'elle soit assez courte et claire. Comment ça marche.
Modifier : 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 morceau de code propre et agréable qui génère une liste de nombres premiers. Je sais déjà comment procéder de différentes manières, mais je suis enclin à écrire du code qui ne soit pas aussi clair que possible. Dans ce fil, quelques bonnes options ont été proposées:
- Une version plus agréable de ce que j’avais au départ (Peter Smit, jmservera et Rekreativc)
- Une mise en oeuvre très propre du tamis d’Ératosthène (étoile bleue)
- Utilisez les
BigIntegeroptions s etnextProbablePrimede Java pour un code très simple, bien que je ne puisse l’imaginer 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 au besoin (darin)
Modifier 2 : j'ai implémenté en C # un couple des méthodes données ici, et une autre méthode non mentionnée ici. Ils trouvent tous les premiers n nombres premiers de manière efficace (et j'ai un méthode décente de trouver la limite à fournir aux tamis).
La solution 2
Un grand merci à tous ceux qui ont apporté 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 de temps en temps, bien que je suppose que ce ne sera pas aussi simple que les méthodes utilisées actuellement. Si quelqu'un peut trouver un moyen d'améliorer l'une de ces méthodes, j'aimerais bien le savoir: -)
Méthode standard ( Peter Smit , jmservera , Rekreativc )
Le premier nombre premier est 2. Ajoutez ceci à une liste de nombres premiers. Le prochain nombre premier est le prochain nombre qui n'est pas divisible par un nombre quelconque de cette liste.
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;
}
Ceci 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 encore être optimisé en testant uniquement les numéros sous la forme 6k+[1, 5], ou 30k+[1, 7, 11, 13, 17, 19, 23, 29] ou so sur .
Tamis d'Eratosthène ( étoile bleu )
Ceci trouve tous les nombres premiers de k . Pour dresser la liste des premiers n nombres premiers, nous devons d’abord approximer la valeur du n e nombre premier. La méthode suivante, comme décrit 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<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;
}
Tamis de Sundaram
Je viens de découvrir ce tamis récemment, mais il peut être implémenté simplement. Mon implémentation n’est pas aussi rapide que le tamis d’Ératosthè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<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;
}
Autres conseils
Utilisez l'estimation
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 quelque peu le nombre de nombres premiers, de sorte que le tamis sera légèrement plus grand que nécessaire, ce qui est correct.
Il s’agit de mon tamis Java standard, calcule le premier million d’amorces en une seconde environ 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;
}
Ressusciter une vieille question, mais je suis tombé dessus en jouant avec LINQ.
Ce code nécessite .NET4.0 ou .NET3.5 avec extensions parallèles
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();
}
Vous êtes sur le bon chemin.
Quelques commentaires
-
prime.Add (3); fait que cette fonction ne fonctionne pas pour nombre = 1
-
Il n'est pas nécessaire de tester la division avec des nombres premiers 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, consultez Algorithmes aléatoires et Miller & # 8211; Test de primalité de Rabin .
Par souci d'exhaustivité, vous pouvez simplement utiliser 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);
}
}
Pas du tout efficace, mais peut-être le plus lisible:
public static IEnumerable<int> GeneratePrimes()
{
return Range(2).Where(candidate => Range(2, (int)Math.Sqrt(candidate)))
.All(divisor => candidate % divisor != 0));
}
avec:
public static IEnumerable<int> Range(int from, int to = int.MaxValue)
{
for (int i = from; i <= to; i++) yield return i;
}
En fait, il ne s’agit que d’une variante de certains articles avec un formatage intéressant.
Je sais que vous avez demandé une solution non-Haskell, mais je l’inclue ici en ce qui concerne la question. Haskell est beau 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 n p = n `mod` p == 0
Utilisez un Générateur de nombres pour créer Prime.txt puis:
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);
}
}
}
Dans ce cas, j'utilise Int16 dans la signature de la méthode. Par conséquent, mon fichier primes.txt contient des nombres compris entre 0 et 32767. Si vous souhaitez étendre cela à Int32 ou Int64, votre prime.txt pourrait être considérablement plus volumineux.
Je peux proposer la solution C # suivante. Ce n'est pas rapide, mais c'est très clair sur ce que ça fait.
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;
}
J'ai laissé de côté tous les contrôles - si la limite est négative ou inférieure à deux (pour le moment, la méthode retournera toujours au moins deux comme valeur de départ). Mais tout cela est facile à réparer.
MISE À JOUR
Avec les deux méthodes d'extension suivantes
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;
}
}
vous pouvez le réécrire comme suit.
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;
}
C’est moins efficace (parce que 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 par la suite les nombres premiers, mais cela encombrera un peu le code.
Voici une implémentation de tamis d'Eratosthenes en C #:
IEnumerable<int> GeneratePrimes(int n)
{
var values = new Numbers[n];
values[0] = Numbers.Prime;
values[1] = Numbers.Prime;
for (int outer = 2; outer != -1; outer = FirstUnset(values, outer))
{
values[outer] = Numbers.Prime;
for (int inner = outer * 2; inner < values.Length; inner += outer)
values[inner] = Numbers.Composite;
}
for (int i = 2; i < values.Length; i++)
{
if (values[i] == Numbers.Prime)
yield return i;
}
}
int FirstUnset(Numbers[] values, int last)
{
for (int i = last; i < values.Length; i++)
if (values[i] == Numbers.Unset)
return i;
return -1;
}
enum Numbers
{
Unset,
Prime,
Composite
}
Copyrights 2009 de St.Wittum 13189 Berlin ALLEMAGNE sous licence CC-BY-SA https://creativecommons.org/licenses/by-sa/3.0/
Le moyen le plus simple mais le plus élégant de calculer ALL PRIMES serait le suivant: mais cette façon est lente et les coûts de la mémoire sont beaucoup plus élevés pour des nombres plus élevés car en utilisant faculty (!) function ... mais cela montre une variation de Wilson Theoreme dans une application pour 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)
En utilisant votre même algorithme, vous pouvez le faire un peu plus rapidement:
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);
}
J'ai écrit une simple implémentation d'Eratosthenes en c # en utilisant un LINQ.
Malheureusement, LINQ ne fournit pas une séquence infinie d'ints, vous devez donc utiliser int.MaxValue: (
Je devais mettre en cache dans un type anonyme le sqrt candidat pour éviter de le calculer pour chaque prime mise en cache (un peu moche).
J'utilise une liste des nombres premiers précédents jusqu'au sqrt du candidat
cache.TakeWhile(c => c <= candidate.Sqrt)
et vérifiez chaque Int à partir de 2 contre
.Any(cachedPrime => candidate.Current % cachedPrime == 0)
Voici le code:
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;
}
}
Une autre optimisation consiste à éviter de vérifier les nombres pairs et à ne renvoyer que 2 avant de créer la liste. Ainsi, si la méthode d’appel demande seulement 1 prime, elle évitera tout le désordre:
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;
}
}
Pour le rendre plus élégant, vous devez refactoriser votre test IsPrime en une méthode distincte, et gérer les boucles 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<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;
}
});
}
});
Voici un exemple de code Python qui affiche la somme de tous les nombres premiers inférieurs à 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 auquel je puisse penser en peu de temps.
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 donner 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 incorrectes pour numberToGenerate < 2. Je tiens simplement à souligner que je n'essayais pas de lui envoyer une excellente méthode pour générer des nombres premiers (regardez la réponse de Henri), je soulignais avec insistance comment sa méthode pouvait être rendue plus élégante.
En utilisant la programmation basée sur les flux dans Java fonctionnel , j’ai proposé ce qui suit. Le type Natural est essentiellement 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()));
Vous avez maintenant une valeur que vous pouvez transporter, qui est un flux infini de nombres premiers. Vous pouvez faire des choses comme ceci:
// 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));
Une explication du tamis:
- Supposons que le premier nombre du flux d'arguments est premier et le placez au début du flux de retour. Le reste du flux de retour est un calcul à produire uniquement sur demande.
- Si quelqu'un demande le reste du flux, appelez sieve sur le reste du flux d'arguments, en filtrant les nombres divisibles par le premier nombre (le reste 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 un assez court & ampli; implémentation propre (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;
}
Essayez cette requête LINQ, elle génère des nombres premiers comme vous le souhaitiez
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("");
La méthode la plus simple est l’essai et l’erreur: vous essayez si un nombre compris entre 2 et n-1 divise le nombre premier de vos candidats.
Les premiers raccourcis sont bien sûr a) il vous suffit de vérifier les nombres impairs, et b) vous ne devez vérifier que les séparateurs allant 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 un des nombres premiers de votre liste, jusqu'à sqrt (n), divise n.
Devrait être le plus rapide que vous pouvez obtenir pour votre argent: -)
modifier
Ok, code, vous l'avez demandé. Mais je vous préviens :-), c'est du 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, vous pouvez utiliser le code Java suivant.
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);
Je l’ai eu en lisant en première lecture de & "Sieve of Atkin &"; sur Wikki plus quelques réflexions préalables que j'ai données à ceci - je passe beaucoup de temps à coder à partir de zéro et suis complètement à zéro sur les gens critiquant mon style de codage très dense semblable à un compilateur + je n'ai même pas fait une première tentative d'exécution le code ... beaucoup de paradigmes que j’ai appris à utiliser sont ici, lisez et pleurez, obtenez ce que vous pouvez.
Soyez absolument & amp; Tout à fait sûr de vraiment tester tout cela avant toute utilisation, bien sûr, ne le montrez à personne - c’est pour la lecture et l’examen des idées. Je dois faire fonctionner l’outil de primalité, c’est donc là que je commence chaque fois que je dois faire fonctionner quelque chose.
Procurez-vous une compilation propre, puis commencez à supprimer ce qui est défectueux - j'ai près de 108 millions de frappes au clavier de code utilisable le faisant 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<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
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("<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();
}
Voici le code 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>
Résultats: 10000 numéros premiers en moins d'une seconde
100 000 numéros premiers en 63 secondes
Capture d'écran des 100 premiers numéros premiers
