Ciurul lui Eratostene - algoritm pentru identificarea tuturor numerelor prime până la un anumit număr întreg Format: Math. care este atribuit matematicianul grec antic Eratosphen Kirensky [1]. Ca și în multe cazuri, este numele algoritmului spune despre principiul funcționării sale, care este, o filtrare sită înseamnă. în acest caz, filtrarea tuturor numerelor, cu excepția simplu. Pe măsură ce trece prin lista de datele șederii și inutile (numite componente) sunt excluse.
Numele Metoda „sită“ este numit astfel deoarece, conform legendei, Eratostene a scris numărul de pe o placă acoperită cu ceară, și găurile străpunse în locurile în care au fost scrise numere compuse. Prin urmare, placa a fost ceva ca o sită prin care „cerne“ toate numerele compuse, și au existat doar simple numere. Eratostene a dat un tabel de numere prime de până la 1000.
Pentru a găsi toate numerele prime nu este mai mare decât un număr n predeterminat. urmând metoda Eratostene, efectuați următorii pași:
- Scrieți toate numere întregi consecutive de la două până la n (2, 3, 4, ..., n).
- Să variabila p este inițial egală cu două - primul număr prim.
- Traversat în lista de numere de la 2p la etapele n numărare de p (acesta va fi un multiplu de p. 2p. 3p. 4p. ...).
- Găsiți primul număr nezachorknutoe în listă, mai mult p. și atribuie o valoare de variabila p este numărul.
- Repetați pașii 3 și 4 până când este posibil.
Acum, toate numărul nezachorknutye în listă - este toate numerele prime de la 2 la n.
În practică, algoritmul poate fi îmbunătățit după cum urmează. În numărul de pasul 3, puteți trece din numărul începând imediat cu numărul 2. p, deoarece toate numerele compuse mai puțin decât ar fi trecut de data asta. Și, în consecință, puteți opri algoritmul atunci când p 2 devine mai mare decât n. [2] De asemenea, toate numerele prime (cu excepția 2) - numere impare, și, prin urmare, ele pot fi considerate ca pași pentru 2p. începând cu p 2.
Complexitatea algoritmului
Complexitatea algoritmului este Operațiuni pentru Tabelul amorsează la [3].
dovada de complexitate
atunci când este selectat pentru fiecare prim Acesta va executa bucla interioară, ceea ce va face acțiuni. Prin urmare, este necesar să se estimeze valoarea următoarea:Deoarece numărul de numere prime. mai mic sau egal , evaluate ca , și, în consecință, -număr prim-lea este aproximativ egal cu , suma poate fi convertită:
Aici, termenul sumei este alocat primului număr prim pentru a preveni diviziunea de la zero. Acum este necesar să se estimeze valoarea integralei:
Rezultatul pentru suma inițială:
O dovadă mai riguroase (și oferă o estimare mai exactă, până la factorii constanți) pot fi găsite în cartea lui Hardy și Wright «O Introducere în teoria numerelor» [4].
implementare optimizată (începând cu pătrate) este pseudocod [5] [6].
Exemplu pentru n = 30
Scriem numerele naturale din șablonul: matematica de până la Format: Math într-un rând:
Primul număr din listă, Format: Math - simplu. Să mergem pe o serie de numere, toate numerele sunt multipli Format zachorkivaya: Math (de exemplu în fiecare secundă, începând cu Format: Math):
Urmatoarea Numere nezacherknutoe Format: Math - simplu. Să mergem pe o serie de numere, toate numerele sunt multipli Format zachorkivaya: Math (de exemplu, la fiecare a treia începe cu Format: Math):
Urmatoarea Numere nezacherknutoe Format: Math - simplu. Să mergem pe o serie de numere, zachorkivaya toate numerele divizibile cu 5 (de exemplu, fiecare a cincea pornire la Format: Math). Și așa mai departe. D.
Numărul următor nezacherknutoe - Format: Math. Sa pătrat, Format: Math - Mai multe Format: Math-ti, astfel încât această lucrare este finalizată. Toate numerele de compozite au trecut deja:
modificarea metodei
, O variație progresivă nelimitat
În acest exemplu de realizare, numere prime sunt calculate secvențial, fără nici o limită superioară ca număr găsit în spațiile dintre numerele de componente care sunt calculate pentru fiecare prim Format: Math. deoarece piața sa, în trepte de câte Format: Math (sau amorse impare Format: Math) [2]. Acesta poate fi reprezentat simbolic în paradigma a modului în care fluxurile de date
separatoare bust
Sita Eratostene adesea confundat cu algoritmi care sunt filtrate din numerele compuse interval stabilite. testarea fiecare dintre numerele de candidat prin separatoare de sortare. [7]
Cunoscut cod funcția David Turner în 1975 [8] este adesea confundat cu sita Eratostene, [7], dar, de fapt, este departe de a fi varianta optimă cu peste separatoare.
sită Euler
Template Sieve Euler: AI este o variantă a sitei de Eratostene, în care fiecare număr compozit este îndepărtat o dată din listă.
Redactat o listă inițială de numere care încep cu Format: Math. La fiecare etapă a algoritmului primul număr din listă este luată ca următorul număr prim, și a determinat lucrările sale pentru fiecare număr din lista care sunt marcate pentru ștergere posleduyushego. După aceea este eliminat din lista primului număr, și toate marcate cu numere, iar procesul se repetă din nou:
Aici este un exemplu începând cu numere impare, după prima etapă a algoritmului. Astfel, după Format: Math -lea etapă iterativ conține doar numărul relativ prim la primul șablon: numere prime Math (adică numere nu sunt divizibile prin oricare din primul șablon: amorse Math) și începe cu Format: Math simplu -lea număr. Toate numerele din listă, pătrat mai mic dintre primele sale numere sunt prime.
Sieve numai în numere impare
Deoarece toate chiar numere. cu excepția 2 - componente, este posibil să nu prelucreze nici un fel, chiar numere și numere impare numai specula. În primul rând, se va reduce cu jumătate din cantitatea de memorie necesară. În al doilea rând, se va reduce numărul de operații efectuate de algoritmul (aproximativ dublu).
Acest lucru poate fi extins la numere nu numai cu 2 prime între ele (adică un număr impar), dar cu 3, 5, și așa mai departe. D.
Reducerea cantității de memorie consumată
Eratostene algoritm funcționează, de fapt, cu biți de memorie. Prin urmare, putem economisi consumul semnificativ de memorie, păstrarea Variabilele booleene nu sunt ca bytes. precum și biți, adică, octeți de memorie.
Această abordare - „compresie biți“ - complică manipularea acestor biți. Orice biți citire sau de scriere vor fi câteva operații aritmetice. Dar, pe de altă parte, îmbunătățește foarte mult compactitatea în memorie. spații mari pot încăpea în memoria cache, care este mult mai rapid decât în mod normal, astfel încât atunci când se lucrează pe un segment general, creste rata.
Sită de Eratostene timpului de funcționare liniară
Acest algoritm detectează fiecare dintre Format: Math în șablonul de segmente: Math împărțitor sale minime de prim Format: Math.
De asemenea, menține o listă a tuturor numerelor prime - o serie de Format: Math. inițial gol. Pe parcursul algoritmului, această matrice va fi umplut treptat.
Inițial, toate valorile de Format: Math umplut cu zerouri.
Apoi, trebuie să sorteze numărul actual de Format: Math de la Format: Math până la Format: Math. Pot exista două cazuri:
- Format: Math. acest lucru înseamnă că numărul de Format: Math - simplu, precum și alte subgrupuri nu a fost găsit pentru el.
- Format: Math. acest lucru înseamnă că numărul actual de Format: Math - compus și prim-împărțitor sa minimă este Format: Math.
In ambele cazuri, procesul de aliniere ulterioară începe valori în șablonul de matrice: Math. ar trebui să ia multipli de Format: Math. și să actualizeze valoarea lor Format: Math. Cu toate acestea, principalul scop - de a învăța cum să-l facă în așa fel încât, în final, fiecare din valoarea Format: Math ar fi setat să nu mai mult de o dată.
Se susține că acest lucru este posibil să facă acest lucru. Considerăm că numărul de șablonul formular: Math. în cazul în care Format: seria Math este egal cu toate numerele prime care nu depășesc Format: Math (doar pentru acest lucru este necesar pentru a păstra o listă a tuturor numerelor prime).
Toate numerele de acest tip pentru a pune în jos noua valoare a Format: Math - ar trebui să fie același model: Math [9].