Descripción del título
Ridbit comienza con un entero n.
En un movimiento, puede realizar una de las siguientes operaciones.
Divida n por uno de sus factores positivos, o…
Si n es mayor que 1, reste 1 de n.
El divisor positivo es el divisor de un número, sin incluirse a sí mismo. Por ejemplo, 1, 2, 4, 5 y 10 son divisores positivos de 20, pero 20 en sí no lo son.
¿Cuántos movimientos debe tener Ridbit al menos para reducir n a 1?
Entrar
La primera línea contiene un número entero t (1≤t≤1000)-el número de casos de prueba.
La única línea de cada caso de prueba contiene un entero n (1≤n≤10^9).
Salida
Para cada caso de prueba, genere el número mínimo de pasos necesarios para reducir n a 1.
Muestra
Entrada
6
1
2
3
4
6
9
Salida
0
1
2
2
2
3
Ideas
Sólo considera números extraños e pares. Primero, tienes que juzgar 1, 2, 3. 1 es 0 pasos, 2 es un paso, y 3 es dos pasos. Los números pares restantes solo necesitan dos pasos, porque todos pueden ser divisibles por 2. Después de que la instrucción de un paso se convierte en 2 y luego menos 1 se convierte en 1. Para los números impares, primero reste 1 y luego se convierta en números pares, como arriba, y luego realice instrucciones de dos pasos, por lo que se requieren tres pasos para números impares.
Código de CA
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int ans=0;
int x;
scanf("%d",&x);
if(x==1||x==2||x==3) ans=x-1;
else if(x&1) ans=3;
else ans=2;
cout<<ans<<endl;
}
return 0;
}
.
