Ciurul lui Eratostene – sursă + problemă rezolvată

[bcman]

Ciurul lui Eratostene este unul dintre algoritmii foarte importan?i ?i este des întâlnit. Acesta este folosit pentru a determina primele n numere prime.

Cerin?a

Spunem c? un numar natural x este prim dac? ?i numai daca x > 1 si singurii s?i divizori sunt 1 si x. Dându-se un numar natural N (2 ? N ? 2 000 000), s? se determine num?rul numerelor prime mai mici sau egale cu N.

Date de intrare

Fi?ierul de intrare ciur.in con?ine o singur? linie pe care se afl? numarul N.

Date de ie?ire

In fisierul de iesire ciur.out se va scrie pe prima linie raspunsul cerut.

Exemplu

Dac? fi?ierul de intrare con?ine num?rul 10, în fi?ierul de ie?ire va trebui s? apar? num?rul 4.

Ideea de baza

În primul rând vom da fiec?rui element din vector valoarea 1, presupunând astfel c? el este prim. Pozi?ia unui element din vector va reprezenta chiar acel num?r. Vectorul este alc?tuit din variabile booleene, astfel, dac? valoarea lui a este egal? cu 1, atunci num?rul i este prim.

Rezolvarea

Vom folosi dou? for-uri pentru a determina dac? num?rul este prim sau nu. Primul începe de la 2 ?i continu? pân? la radical din n. Al doilea este inclus în primul ?i face parcurgerea de la i pân? la n/i. Apoi, fiecare num?r care se ob?ine prin intermediul produsului acestor 2 numere este eliminat, el nemaiputând fi prim pentru c? are divizori. În sfâr?it, un for final va parcurge vectorul de la 2 pân? la n, iar pentru fiecare num?r a c?rui corespondent din vector este 1 contorul (ini?ializat cu 0) va fi incrementat. Apoi se va face afi?area contorului, adic? a num?rului de numere prime mai mici ca n.

Continuarea articolului pe: Ciurul lui Eratostene - surs? + problem? rezolvat? | WorldIT