Practică & Proiecte

Exemple practice

Câteva probleme clasice rezolvate complet, care reunesc conceptele din curs.

1. Ciurul lui Eratostene

const int N = 1000000;
bool compus[N+1] = {};
vector<int> prime;

for (int i = 2; i <= N; i++) {
  if (!compus[i]) {
    prime.push_back(i);
    for (long long j = (long long)i*i; j <= N; j += i)
      compus[j] = true;
  }
}
cout << "Prime pana la " << N << ": " << prime.size() << endl;

2. GCD (cmmdc) și LCM (cmmmc)

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

cout << gcd(12, 18) << endl;  // 6
cout << lcm(4, 6)   << endl;  // 12

3. Sortare prin selecție

void selSort(int v[], int n) {
  for (int i = 0; i < n-1; i++) {
    int minIdx = i;
    for (int j = i+1; j < n; j++)
      if (v[j] < v[minIdx]) minIdx = j;
    swap(v[i], v[minIdx]);
  }
}