Question

1. Sa se afiseze numerele prime pana la n , unde n este numar natural cu cel mult 4 cifre citite de la tastatura.
2. Sa se afiseze numerele prime din intervalul [a, b], unde a, b sunt numere naturale cu cel mult 4 cifre citite de la tastatura.

Vreau rezolvarea ambelor probleme cu ''CIURUL /SITA LUI ERATOSTENE'' + explicatie, va rog!
Multumesc!

Answer 1

Inainte de a trece la partea de informatica: un mod vizual de a intelege Ciurul lui Eratostene:
-Gandeste-te ca vrei sa afli  toate numerele prime de la 1 la 100.(Ai putea sa-l iei pe fiecare si sa-l verifici, dar asta iti va lua mult)
-Scrie pe o foaie toate numerele de la 1 la 100
-Incepe de la primul numar prim, care este 2(pe 1 il vom elimina din sir automat)
-Stii ca 2 este prim, dar mai stii ca toti ceilalti multiplii ai lui 2 nu sunt primi, astfel: 4, 6, 8, 10, ..., 100 - nu sunt numere prime ==> Tai acele numere de pe foaie
-Te duci la urmatoul numar care NU este taiat si stii ca acela nu este prim, apoi aplici aceeasi regula. (in continuare vei ajunge la 3 si vei taia numerele 6, 9, 12, ..., 99 - divizibile cu 3)
-Continui acest proces pana cand ajungi la sfarsit. Numerele care nu au fost taiate sunt numere prime


Partea informatica: Se declara un vector care la inceput are toate elementele 0, unde  fiecare element al vectorului corespunde indicelui sau, si parcurgem vectorul de la 2 la 100. Daca un element v[i] din vector este 0, vom egala cu 1 toate elementele: v[2 * i], v[3 * i], v[4 * i], ....

Ai solutiile problemelor in atasament

4b02c259249d53b8e84ef9e2adb93ed7.cpp

6057dc002b3d27d27d2dae6d4f1926ed.cpp

Answer 2

Iti ofer si solutia mea la ciurul lui Eratostene. Succes!
problema 1)
#include <bits/stdc++.h>
#define NMax 10015
using namespace std;
int n, i, j, nr, x;
bool w[NMax];
int main()
{
    cin >> n;
    for(i = 2; i <= NMax; i ++)
     if(w[i] == false)
     {
      cout << i << " ";
      for(j = i * i; j <= NMax; j = j + i)
       w[j]=true;
     }
    return 0;
}
 problema 2)
La aceasta problema ciurul este putin diferit (mai eficient - decat primul)
#include <bits/stdc++.h>
#define NMax 10015
using namespace std;
int a, b, i, j, nr, x;
bool w[NMax];
int main()
{
    for(i = 2; i * i <= NMax; i++)
     if(w[i] == false)
      for(j = i * i; j <= NMax; j = j + i)
       w[j]=true;
    w[1] = w[0] = true;
    cin >> a >> b;
    for(i = a; i <= b; i ++)
     if(w[i] == false) cout << i << " ";
    return 0;
}