Se debe determinar el numero de pasos minimos para que un entero N llegue a 0, siguiendo estas reglas: 1) Si N es el producto de dos numeros a y b, distintos de 1, entonces remplazar N por el max(a,b) 2) De lo contrario, remplazar N por N-1
Ejemplo: El numero 36 tiene 5 pasos para llegar a 0 porque:
36-->6-->3-->2-->1-->0
Esto porque 36=6*6, N cambia al maximo (6). Luego 6=3*2, N cambia al maximo (3). Notar que si en 36 se hubieran tomado a y b como 18 y 2, entonces el numero de pasos habria sido 6, por lo que no seria el minimo
36-->18-->9-->3-->2-->1-->0
Entrada: Un entero Q que sera el numero de casos a evaluar, junto a Q veces el entero N que queremos evaluar. Salida: Numero mínimo de pasos para llevar cada numero a 0
Intento de solucion: #include #include
using namespace std;
int Q, N, i, a, b;
int main(){
cin>> Q;
for (i=0;i<Q;i++){
cin>>N;
int contador = 0;
int l = N;
for (int k=0;k<N;k++){
if (l>0 && l == a*b){
l=max(a,b);
contador ++;
}
else if (l>0){
l=l-1;
contador ++;
}
}
cout<<contador<<endl;
}
return 0;
}
No obstante, no supe como determinar los dos numeros a y b que multiplicados den N.