== include(page="template/taskheader" task_id="sieve") ==

Poveste şi cerinţă...

//Povestea va fi schimbata
 
In aceasta problema vom analiza cum se comporta Ciurul lui Eratosthene daca in loc sa parcurgem numerele in ordinea {2, 3, 4, .. N}, le parcurgem in ordinea data de o permutare aleatoare a acestor numere. Mai exact, dandu-se acest pseudocod:
 
== code(c) |
int countSteps(int n, vector<int> p) {
    vector<bool> Composite(n + 1, false);
    int steps = 0;
 
    // p este o permutare a multimii {2, 3, ..., n}
 
    for(int index = 0; index < n - 1; ++index) {
        if(not Composite[p[index]]) {
            for(int multiple = 2 * p[index]; multiple <= n; multiple += p[index]) {
                Composite[multiple] = true;
                steps += 1;
            }
        }
    }
 
    return steps;
}
==

h2. Date de intrare