Tamis d'Eratosthène au-delà de O (n). Preuve

Dans les commentaires à l'un des articles précédents sur le tamis d'Eratosthène, ce court algorithme de Wikipedia a été mentionné:

Algorithme 1:

1:  i := 2, 3, 4, ...,  n: 2:  lp[i] = 0: 3: lp[i] := i 4: pr[] += {i} 5:  p  pr  p ≤ lp[i]  p*i ≤ n: 6: lp[p*i] := p : lp -        n pr -     n. 

L'algorithme est simple, mais il ne semble pas évident à tout le monde. Le principal problème est qu'il n'y a aucune preuve sur Wikipedia, et le lien vers la source ( pdf ) contient un algorithme assez différent de ce qui précède.

Dans cet article, j'essaierai, j'espère, qu'il est possible de prouver que cet algorithme fonctionne non seulement, mais le fait également pour la complexité linéaire.

Définitions

$$$\ mathcal {P}$ - beaucoup de nombres premiers.
$$$lp (x)$ - diviseur premier minimal d'un nombre: $$$lp (x) = min \ {p \ in \ mathcal {P} \ \ vert \ p \ vert x \}$
$$$rd (x)$ - autres facteurs: $$$rd (x) = x / lp (x)$

Veuillez noter que toutes les définitions ci-dessus sont pour $$$x \ ge 2$ .

Quelques propriétés évidentes des fonctions présentées ci-dessus, qui seront utilisées plus tard:
$$$lp (a \ fois b) = min (lp (a), lp (b))$
$$$rd (x) <x$
$$$p \ in \ mathcal {P} => lp (p) = p$

Preuve

Lemme 1 : $$$lp (x) \ le lp (rd (x)), \ forall x \ notin \ mathcal {P}, x> 1$
Preuve : Parce que tout diviseur $$$rd (x)$ aussi un diviseur $$$x$ et $$$lp (x)$ pas supérieur à n'importe quel diviseur $$$x$ alors $$$lp (x)$ ne dépasse aucun diviseur $$$rd (x)$ y compris le plus petit d'entre eux. Le seul problème avec cette déclaration est si $$$rd (x)$ n'a pas de diviseurs simples, mais cela n'est possible que si $$$x \ in \ mathcal {P}$ , ce qui est exclu dans l'état du lemme.
$$$\ carré$

Soit $$$E = \ {(lp (x), rd (x)) \ vert \ forall x \ notin \ mathcal {P}, 2 \ le x \ le n \}$

Parce que $$$lp (x) \ fois rd (x) = x$ (par définition $$$rd ()$ ), si on nous donnait beaucoup $$$E$ alors nous pourrions calculer $$$lp ()$ pour tous les nombres composites jusqu'à n. Cela se fait, par exemple, par l'algorithme suivant:

Algorithme 2:

 1:   (l,r)  E: 2: lp[l*r] := l; 

Notez que $$$\ vert E \ vert \ le n$ donc l'algorithme 2 ci-dessus fonctionne pour la complexité linéaire.

De plus, je prouverai que l'algorithme 1 de Wikipedia itère en fait juste sur tous les éléments de cet ensemble, car il peut être paramétré d'une manière différente.

Soit $$$E '= \ {(p, r) \ vert p \ in \ mathcal {P}, 2 \ le r <n, p \ le lp (r), p \ times r \ le n \}$

Lemme 2 : $$$E = E '$
Preuve :

Soit $$$(a, b) \ en E$ => $$$\ existe x \ notin \ mathcal {P}, \ 2 \ le x \ le n \ mid a = lp (x), b = rd (x)$ .

Par définition $$$lp (), rd ()$ : $$$a \ in \ mathcal {P}$ , $$$a \ fois b = x$ . Par le lemme 1, $$$a \ le lp (b)$ .
parce que $$$rd (x) <x$ alors $$$b <n$ .
Depuis $$$x \ notin \ mathcal {P}$ , $$$b \ ge 2$ .
Aussi, par définition $$$E$ , $$$x \ le n$ donc $$$a \ times b \ le n$ .
Les 4 conditions $$$E '$ moyens remplis $$$(a, b) \ in E '$ => $$$E \ sous-ensemble E '$ .

Soit $$$(a, b) \ in E '$ . Soit $$$x = a \ fois b$ .
Par définition $$$E '$ , $$$a \ in \ mathcal {P}$ . Moyens $$$a$ - division simple $$$x$ .
$$$lp (x) = lp (a \ fois b) = min (lp (a), lp (b)) = min (a, lp (b)).$
Parce que $$$a \ le lp (b)$ alors $$$lp (x) = a.$ Moyens $$$b = rd (x).$
Par définition, $$$x = a \ fois b \ le n.$ De toute évidence aussi $$$x = a \ fois b \ ge 2.$
Toutes les conditions pour $$$E$ terminé => $$$E '\ sous-ensemble E.$

Par conséquent $$$E = E '.$
$$$\ carré$

Reste maintenant à trier les bons $$$r$ et $$$p$ de la définition de l'ensemble $$$E '$ et appliquer l'algorithme 2. C'est exactement ce que fait l'algorithme 1 (seule la variable i est utilisée au lieu de r). Mais il y a un problème! Pour trier tous les éléments d'un ensemble $$$E '$ calculer $$$lp,$ nous devons savoir $$$lp,$ car il y a une condition dans la définition $$$p \ le lp (r)$ .

Heureusement, ce problème contourne le bon ordre de tri. Il faut trier $$$r$ dans la boucle extérieure, et $$$p$ - à l'intérieur. Alors $$$lp (r)$ sera déjà calculé. Ce fait est prouvé par le théorème suivant.

Théorème 1:
L'algorithme 1 prend en charge l'invariant suivant: après itération de la boucle externe pour i = k, tous les nombres premiers jusqu'à k inclusivement seront mis en évidence dans pr. Sera également compté $$$lp ()$ pour tous $$$x \ notin \ mathcal {P} \ mid x \ le n, \ rd (x) \ le k$ dans le tableau lp.

Preuve :
Nous prouvons par induction. Pour k = 2, l'invariant est vérifié manuellement. Le seul premier 2 sera ajouté à la liste pr, car le tableau lp [] est initialement rempli de zéros. De plus, le seul numéro composé dans lequel $$$rd (x) \ le 2$ - c'est 4. Il est facile de vérifier que la boucle interne s'exécutera exactement une fois (pour n> 3) et exécutera correctement lp [4]: ​​= 2.

Supposons maintenant que l'invariant soit valable pour l'itération i = k-1. Prouvons qu'il sera également valable pour l'itération i = k.

Pour cela, il suffit de vérifier que le nombre i, s'il est premier, sera ajouté à la liste pr et que $$$lp ()$ sera compté pour tous les nombres composites $$$x \ le n,$ dont $$$rd (x) = i.$ Ce sont ces nombres de l'invariant pour k qui ne sont pas déjà couverts par l'invariant pour k-1.

Si i est simple, alors lp [i] sera 0, car la seule opération d'écriture dans le tableau lp, qui pourrait théoriquement calculer lp [i] (à la ligne 6), écrit toujours dans des indices composites, car p * i (pour i> 1) - toujours composé. Par conséquent, le nombre i sera ajouté à la liste des nombres premiers. De plus, à la ligne 3, lp [i] sera compté.

Si i est composite, alors au début de l'itération lp [i] sera déjà calculé par l'invariant pour i = k-1, car $$$rd (i) <i$ ou $$$rd (i) \ le i-1,$ par conséquent, i tombe sous la condition invariante dans l'itération précédente. Par conséquent, le nombre composite i ne sera pas ajouté à la liste des nombres premiers.

De plus, ayant le lp [i] correct et tous les nombres premiers jusqu'à i inclus, la boucle des lignes 5-6 itérera sur tous les éléments $$$(p, i) \ in E '$ dans laquelle la deuxième partie est i:

• $$$p \ in P,$ car c'est de la liste pr
• $$$p \ le lp (i),$ par condition d'arrêt du cycle
• $$$p \ fois i \ le n,$ par condition d'arrêt du cycle
• $$$i <n,$ découle de $$$p \ fois i \ le n, \ p> 1$

Tous les nombres premiers nécessaires dans la liste pr sont, car seulement des nombres jusqu'à $$$lp (i) \ le i$ . Par conséquent, les valeurs de lp [] seront calculées pour tous les nombres composites $$$x$ pour lequel $$$rd (x) = i$ . Ce sont exactement tous les nombres qui manquaient lors de la transition de l'invariant pour k-1 à l'invariant pour k.

Par conséquent, l'invariant est valable pour tout i = 2..n.

$$$\ carré$

Par l'invariant du théorème 1 pour i = n, il s'avère que tous les nombres premiers jusqu'à n et tous les lp [] seront calculés par l'algorithme 1.

De plus, puisque dans les lignes 5-6, divers éléments de l'ensemble sont triés $$$E$ , alors la boucle interne totale ne s'exécutera plus $$$\ vert E \ vert <n$ opérations. L'opération de vérification dans la boucle se déroulera sans problème $$$\ vert E \ vert + n - 1 <2n$ fois ( $$$\ vert E \ vert$ fois renverra vrai et n-1 fois, pour chaque i, retournera faux). Toutes les opérations restantes sont imbriquées dans un cycle en i de 2 à n.
Il s'ensuit que la complexité de l'algorithme 1 est O (n).