Tamis Sundarama

Le tamis Sundarama dans le réseau est représenté par un grand nombre de sources d'informations brèves. Néanmoins, j'ai décidé d'énoncer ce que j'aimerais lire moi-même au début de l'étude des algorithmes de la théorie des nombres.

Le tamis de Sundarama est l'une des trois méthodes les plus connues pour générer des nombres premiers. Maintenant, il est habituel de le traiter comme un peu exotique en raison de la faible complexité de calcul: O (N (logN)). Cependant, les asymptotiques sont asymptotiques et, dans la pratique, dans la plage de tamisage 32 bits, Atkin, par exemple, ne dépasse Sundaram qu'avec une optimisation minutieuse.

Les implémentations du tamis Atkin, circulant sur Internet, ne dépassent pas le tamis Sundaram ni en termes de temps, ni en termes d'efficacité de mémoire. La méthode Sundaram peut donc être utilisée comme outil auxiliaire dans des expériences avec des algorithmes plus avancés.

Le tamis de Sundarama trouve tous les nombres premiers dans une plage donnée de nombres naturels 3 ≤ n ≤ N "filtrant" les composants. Sans perte de généralité, la valeur de N peut être considérée comme impaire. Si N est pair, alors il est garanti d'être composite, et il peut être exclu de la plage de tamisage en diminuant la valeur de la limite supérieure d'une unité.

L'algorithme est basé sur le fait suivant. Tout nombre composite impair n peut être représenté comme le produit de deux nombres impairs naturels supérieurs à un:

(1) n = (2 * i + 1) * (2 * j + 1),

où i et j sont des nombres naturels (zéro n'est pas un nombre naturel). Il est impossible d'imaginer un nombre premier n sous cette forme, car sinon cela signifierait que n a des diviseurs supplémentaires en plus de lui et un.

Nous écrivons le n impair sous la forme 2 * m + 1, le substituons dans (1) et obtenons l'expression de m:

(2) m = 2 * i * j + i + j.

Cette transformation conduit directement à l'idée du tamis de Sundaram.

Afin de filtrer les nombres composites d'un intervalle donné, vous devez utiliser un tableau dans lequel un élément d'index m est représentatif du nombre 2 * m + 1. Après avoir organisé l'énumération des valeurs des variables i et j, nous calculerons l'indice m selon la formule (2), et dans le correspondant les éléments du tableau définissent la marque "nombre composite". Une fois l'énumération terminée, tous les nombres composites de la plage seront marqués et les nombres premiers peuvent être sélectionnés par l'absence de marque.

Reste à clarifier les détails techniques.

Sur la base du raisonnement précédent, pour représenter la limite supérieure (impaire) de la plage de tamisage N, l'indice m prend sa valeur maximale mmax = (N - 1) / 2. Cela détermine la taille requise de la baie.

Nous énumérerons les valeurs de i et j en deux cycles: une boucle externe pour énumérer les valeurs de i et une boucle interne imbriquée pour les valeurs de j.

La valeur initiale du compteur de boucle externe est i = 1. Étant donné la symétrie complète de l'occurrence des variables i et j dans l'expression (2), pour éviter des calculs répétés en double, le cycle interne doit commencer par la valeur j = i.

Trouvez la valeur maximale pour le compteur de boucle externe imax ≥ i. Si la limite de la plage N est un nombre composé impair, alors avec la valeur i = imax, la boucle interne doit être exécutée au moins une fois avec la valeur de son paramètre j = imax pour supprimer N, et l'expression (2) prendra sa valeur maximale:

mmax = 2 * imax * imax + imax + imax,
imax ^ 2 + imax - mmax / 2 = 0.

En résolvant cette équation quadratique, nous obtenons: imax = (√ (2 * mmax + 1) -1) / 2 = (√N-1) / 2.
La restriction pour le compteur du cycle interne jmax ≥ j résulte de l'inégalité
mmax ≥ 2 * i * j + i + j , d'où nous obtenons: jmax = (mmax - i) / (2 * i + 1).

Les valeurs des limites supérieures doivent être arrondies à la valeur entière la plus proche, en éliminant la partie fractionnaire.

Ce qui suit est une liste d'une classe Sundaram C # très simple qui implémente la méthode décrite.

using System; using System.Collections; namespace CSh_Sundaram { public class Sundaram { public double dt; //   () private long t1; //   private long t2; //   private uint limit; //     private int arrlength; //   private BitArray Prim; //    private int counter; public Sundaram(uint _limit) { limit = _limit; if (limit % 2 == 0) limit -= 1; arrlength = (int)(limit / 2); Prim = new BitArray(arrlength); t1 = DateTime.Now.Ticks; Sieve(); //  t2 = DateTime.Now.Ticks; dt = (double)(t2 - t1) / 10000000D; counter = -1; } public uint NextPrime { get { while (counter < arrlength - 1) { counter++; if (!Prim[counter]) return (uint)(2 * counter + 3); } return 0; } } private void Sieve() { int imax = ((int)Math.Sqrt(limit) - 1) / 2; for (int i = 1; i <= imax; i++) { int jmax = (arrlength - i) / (2 * i + 1); for (int j = i; j <= jmax; j++) { Prim[2 * i * j + i + j - 1] = true; } } } } } 

En tant que paramètre lors de la création d'un objet de type Sundaram, la limite supérieure de la plage de tamisage est indiquée. Pour le tri, la classe utilise un tableau de type BitArray. Cela augmente le temps d'exécution, mais vous permet de couvrir toute la plage 32 bits du type uint. Le tri est effectué lors de l'accès à la méthode Sieve () à partir du constructeur de classe. Une fois terminé, le champ dt contiendra le temps d'exécution de Sieve en secondes.

Lors de l'accès à la propriété NextPrime, séquentiellement, à partir de 3, dans l'ordre croissant, les nombres premiers seront retournés. Une fois tous les simples de la plage épuisés, la valeur 0 sera renvoyée.