Ciurul lui Eratostene - algoritm pentru identificarea tuturor numerelor prime până la un număr întreg, care este atribuit matematicianul grec antic Eratostene Kirensky.
algoritmul Editare
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.
- Șters din lista tuturor numerelor de la 2p la n. divizibil cu p (de exemplu, numărul de 2p. 3p. 4p. ...)
- Găsiți mai întâi nu barată număr mai mare decât p. și atribuie o valoare de variabila p este numărul.
- Repetați pașii 3 și 4 până la până când nu p devine mai mare decât n
- Nu este trecut din listă - numerele prime.
În practică, algoritmul poate fi îmbunătățit ușor în felul următor. №3 pe pas, puteți trece afară numărul, începând imediat cu numerele, deoarece toate numerele compuse mai puțin decât trebuie să fie șters în acest moment. Și, în consecință, vă puteți opri algoritmul, când va fi mai mult.