Ciurul lui Eratostene – sursă + problemă rezolvată

Sift the Two’s and sift the Three’s, The Sieve of Eratosthenes. When the multiples sublime, The numbers that remain are Prime.

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[i] 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.

Codul

#include <fstream>
#include <math.h>

using namespace std;

int main() {
ifstream fin;
ofstream fout;
fin.open("ciur.in");
fout.open("ciur.out");
bool a[2000001];
int nr=0, n, i, j;
fin>>n;
for (i=2;i<=n;i++)  
  a[i]=1;
for (i=2;i<=sqrt(n);i++)
 if (a[i])
  for (j=i;j<=n/i;j++)
     a[i*j]=0;
for (i=2;i<=n;i++)
  if (a[i]) nr++;
fout<<nr;
fout.close();
return 0;
}

Problemă demonstrativă

În continuare vă voi prezenta o problemă de pe infoarena care se rezolvă cu ajutorul ciurului lui Eratostene.

Enunţ

Gheorghe a învățat la școală despre numere prime. A învățat că un număr este prim, dacă se divide doar cu 1 și cu el însuși(1 nu este considerat număr prim). A aflat că există algoritimi foarte eficienți care pot determina dacă un număr este prim sau nu, în timp chiar sub polinomial. Din păcate acești algoritmi sunt foarte complicați, și Gheorghe s-a gândit la o aproximare. Ideea lui este să consideri un număr prim dacă nu se divide la primele K numere prime.

Cerinţă

Demonstrează că ideea lui Gheorghe este doar o aproximare. Dându-se un număr K (1 ≤ K ≤ 100.000), află cel mai mic numar N care nu este divizibil cu primele K numere prime, dar nu este prim.

Date de intrare

Pe prima linie din fişierul prim.in se va afla numărul K.

Date de ieşire

Pe prima linie a fişierului prim.out se va gasi numarul N căutat.

Exemplu

Pentru valoarea 3 ca dată de intrare se va afișa 49, pentru că primele 3 numere prime sunt 2, 3, 5. Numerele care nu sunt divizibile cu 2, 3 sau 5 sunt : 7, 11, 13, 17, 19, 23, 31, 37, 41, 47, 49, .. 49 este cel mai mic numar care nu este prim.

Rezolvare

Deoarece nu știm de câte numere vom avea nevoie, am preferat să folosesc un define pentru 1.500.000, acest număr fiind „capătul” vectorului. Până acolo vom face parcurgerea vectorului, aplicând Ciurul lui Eratostene. Variabila nrp desemnează numărul de parcurgeri, astfel, când se ajunge la k+1 parcurgeri n va lua valoarea pătratului lui i, până atunci multiplii lui i fiind „eliminaţi”, valoarea lor din vector devenind 0. Condiția de la început  if(prim[i])  se asigură că se vor verifica doar numerele reale. Datorită faptului că pătratul unui număr prim nu se poate divide la numărul prim anterior, ne dăm seama că soluția i*i după k+1 parcurgeri este cea corectă.

Codul

#include <fstream>
#include <math.h>
#define INF 1500000

using namespace std;

bool prim[INF];

int main(){
ifstream fin("prim.in");
ofstream fout("prim.out");
long long n,k,nrp,i,j;
fin>>k;
for(i=2;i<INF;i++)
  prim[i]=1;
for(i=2,nrp=0;i<=INF;i++)
  if(prim[i]){
    if(++nrp==k+1){
      n=(long long)i*i;
      fout<<n;
      fout.close();
      return 0;
    }    
    for(j=i;j<=INF;j+=i)
      prim[j]=0;
  }
}

Sursa: Ciurul lui Eratostene. Problema demonstrativă.