2015 – 6

Si consideri la seguente funzione:

int mistero(int x)
{
    int j=2, i, 
    m=x;
    int v[100];
    for(i=0; i <= x+1; i++)
       v[i]=1;
    while (j*j <= x) 
    {
       for(i=1; i <= x+1; i++)
       {
          if(j*i <= x+1)
             v[j*i]=0;
       }
       j++;
    }
    while(v[m] == 0) 
        m--;
    return m;
}

Cosa restituisce la funzione mistero() se viene chiamata passandole il valore x uguale a 40?

Soluzione: 37.

Il primo for() inizializza a 1 per i=0..41.

[1, 1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,  1,1,1,1,1,1,1,1,1,1, 1]

Il ciclo while() scorre i valori di j tali che j*j <= 40, quindi =2..6.
Per ogni valore di j assegna 0 alle posizioni che sono multipli: j, 2j, 3j, ...

• j=2, [1, 1,0,1,0,1,0,1,0,1,0, 1,0,1,0,1,0,1,0,1,0, 1,0,1,0,1,0,1,0,1,0,  1,0,1,0,1,0,1,0,1,0, 1]
• j=3, [1, 1,0,0,0,1,0,1,0,0,0, 1,0,1,0,0,0,1,0,1,0, 0,0,1,0,1,0,0,0,1,0,  1,0,0,0,1,0,1,0,0,0, 1]
• j=4, ...
• j=5, [1, 1,0,0,0,0,0,1,0,0,0, 1,0,1,0,0,0,1,0,1,0, 0,0,1,0,0,0,0,0,1,0,  1,0,0,0,0,0,1,0,0,0, 1]
• j=6, ...

L'ultimo while() scorre i valori al contrario, se il valore è 0. partendo dalla posizione 40.

[1, 1,0,0,0,0,0,1,0,0,0, 1,0,1,0,0,0,1,0,1,0, 0,0,1,0,0,0,0,0,1,0,  1,0,0,0,0,0,1,0,0,0, 1]

Il primo valore 1 si trova alla posizione 37.