Ekran Eratostenesa

Sito Eratostenesa jest sposób znaleźć wszystkie liczby pierwsze poniżej pewnej liczby naturalnej danego N . Ekran Atkin jest szybszy, ale bardziej złożony.

Algorytm

Algorytm działa przez eliminację: polega na usunięciu z tabeli liczb całkowitych od 2 do N wszystkich wielokrotności liczby całkowitej (innej niż siebie).

Usuwając wszystkie te wielokrotności, na końcu pozostaną tylko liczby całkowite, które nie są wielokrotnościami żadnej liczby całkowitej z wyjątkiem 1 i siebie samych, a zatem są liczbami pierwszymi.

Zaczynamy od wykreślenia wielokrotności 2, następnie pozostałych wielokrotności 3, następnie pozostałych 5 wielokrotności i tak dalej, wykreślając za każdym razem wszystkie wielokrotności najmniejszej pozostałej liczby całkowitej.

Możemy przestać, gdy kwadrat najmniejszej pozostałej liczby całkowitej jest większy od największej pozostałej liczby całkowitej, ponieważ w tym przypadku wszystkie liczby inne niż pierwsze zostały już wcześniej wykreślone.

Na końcu procesu wszystkie liczby całkowite, które nie zostały przekreślone, są liczbami pierwszymi mniejszymi od N.

Poniższa animacja ilustruje sito Eratostenesa dla N = 120:

Uwaga: jeśli składa się liczba n , to n = n 1 n 2 , z koniecznością co najmniej jednego z dzielników n i mniej niż . Dlatego na powyższym sicie, na którym wybraliśmy 120, ponieważ 121 = 11², zatrzymujemy się po znalezieniu wielokrotności 7.

Przykłady wdrożeń IT

Sito Eratostenesa można zaimplementować w sposób klasyczny lub rekurencyjny, ale także w postaci metody potokowej .

Pseudo kod

W wersji klasycznej przepisujemy algorytm w następujący sposób:

Fonction Eratosthène(Limite) L = tableau de booléen de taille Limite, initialisé à Vrai L[1] = Faux Pour i de 2 à Limite Si L[i] Pour j de i*i à Limite par pas de i on peut commence à i*i car tous les multiples de i inférieurs à i*i ont déjà été rayés L[j] = Faux Fin pour Fin si Fin pour Retourner L Fin fonction

Podobnie jak w powyższej animacji, możemy zoptymalizować poprzedni kod, zatrzymując raz pętlę For i, i*i>Limiteponieważ nie będziemy już wchodzić do pętli For j i po prostu wyświetlając indeksy L zawierające True.

Fonction Eratosthène(Limite) L = tableau de booléen de taille Limite, initialisé à Vrai L[1] = Faux i=2 Tant que i*i≤Limite Si L[i] Pour j de i*i à Limite par pas de i on peut commence à i*i car tous les multiples de i inférieurs à i*i ont déjà été rayés L[j] = Faux Fin pour Fin si i=i+1 Fin tant que Retourner L Fin fonction

Możemy też uniknąć kilkukrotnego sprawdzania liczb parzystych i podzielić czas realizacji przez 2

Fonction Eratosthène(Limite) L = tableau de booléen de taille Limite, initialisé à Vrai Mettre à Faux les cases d'indice pair > 2 L[1] = Faux i=3 Tant que i*i≤Limite Si L[i] Pour j de i*i à Limite par pas de 2*i L[j] = Faux Fin pour Fin si i=i+1 Fin tant que Retourner L Fin fonction

Wersja rekurencyjna

Sito Eratostenesa można łatwo zakodować za pomocą funkcji rekurencyjnej, którą wystarczy wywołać na początku tablicą liczb całkowitych od 2 do N.

Oto pseudokod:

FONCTION Eratosthène( entiers ) SI premier entier au carré > dernier entier ALORS AFFICHE entiers SINON AFFICHE premier entier EXECUTE Eratosthène( tous les entiers non multiples du premier entier ) FIN SI FIN FONCTION

Algorytm rekurencyjny ma tę zaletę, że może być kodowany w języku, który nie obsługuje struktury danych typu listy.

Wersja rurociągu: The Hoare Screen (1978)

Chodzi o to, aby wygenerować każdą liczbę do sprawdzenia i przekazać ją do sortowania kaskadowego, zachowując otrzymane liczby całkowite tylko te, które są pierwsze.

W tym celu, do każdej splamionej liczby pierwszej przypisana jest pozycja, która będzie przekazywać swoim następcom tylko te, które nie są jej wielokrotnościami.

Ten system nie używa tabeli ani listy liczb do przetworzenia a priori , ale w dowolnym momencie stacji (aktywnej komórki lub programu ) na już rozpoznaną liczbę pierwszą .

Crible de C.A.R HOARE : Un GENERATEUR passe chaque entier de 2 à N au premier poste disponible(qu'il crée s'il n'existe pas). Pour chaque POSTE créé : * il conserve le premier entier qu'il reçoit, disons p, * puis il transmet au poste suivant (créé si besoin) tout entier reçu n non divisible par p.

Więc :

Przy prędkości przelotowej sito to zaczyna sprawdzać pierwotność nowych liczb, kontynuując lub kończąc sprawdzanie pierwotności poprzednich liczb .

Zauważmy, że jeśli nie ma maszyny równoległej z procesorami, ta metoda jest nieefektywna, ponieważ każda stacja przechodzi przez liczbę liczb całkowitych rzędu n.

Uwagi i odniesienia

CAR Hoare, Komunikowanie procesów sekwencyjnych , CACM 21 (1978) str.  666-677

Κόσκινον Ερατοσθένους lub Sito Eratostenesa. Będąc relacją z jego metody znajdowania wszystkich liczb pierwszych , ks. Samuel Horsley, FRS, Philosophical Transactions (1683-1775), tom. 62. (1772), str.  327-347 .

Załączniki

Powiązane artykuły

Linki zewnętrzne

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">