CF1451A-Subtract or Divide

题目:

题目描述:

Ridbit starts with an integer $ n $ .

In one move, he can perform one of the following operations:

• divide $ n $ by one of its proper divisors, or
• subtract $ 1 $ from $ n $ if $ n $ is greater than $ 1 $ .

A proper divisor is a divisor of a number, excluding itself. For example, $ 1 $ , $ 2 $ , $ 4 $ , $ 5 $ , and $ 10 $ are proper divisors of $ 20 $ , but $ 20 $ itself is not.

What is the minimum number of moves Ridbit is required to make to reduce $ n $ to $ 1 $ ?

输入格式:

The first line contains a single integer $ t $ ( $ 1 \leq t \leq 1000 $ ) — the number of test cases.

The only line of each test case contains a single integer $ n $ ( $ 1 \leq n \leq 10^9 $ ).

输出格式:

For each test case, output the minimum number of moves required to reduce $ n $ to $ 1 $ .

样例:

样例输入1:

1
2
3
4
5
6
7

6
1
2
3
4
6
9

样例输出1:

1
2
3
4
5
6

0
1
2
2
2
3

思路:

实现:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#include "ybwhead/ios.h"

int main()
{
	int TTT;
	yin>>TTT;
	while(TTT--)
	{
		int n;
		yin>>n;
		if(n==1){puts("0");continue;}
		if(n==3)
		{
			puts("2");
			continue;
		}
		if(n==2)
		{
			puts("1");
			continue;
		}
		if(n&1)
		{
			puts("3");
			continue;
		}
		else
		{
			puts("2");
		}
	}
	return 0;
}