hpuoj--1410--QAQ & 火星情报局

矫情吗；* 2022-06-10 12:22 115阅读 0赞

## 问题 C: QAQ & 火星情报局 ##

时间限制: 1 Sec  内存限制: 128 MB  
  
提交: 220  解决: 25

## 题目描述 ##

QAQ~超级喜欢看火星情报局，每周六都是他一周中最期待的一天，QAQ喜欢和自己一样心愿是“世界和平”的薛之谦，

喜欢“一言不合就飙车”的宇哥，喜欢“再扯的提案都能升华为鸡汤”的汪涵局长....当然也喜欢的里面各种各样奇葩有趣的提案.....

![20170810193853_22503.jpg][]

最近 K 星颁布了一项新的法律，所有 K 星的公民必须缴纳的所得税是收入 `money` 的最大因子 `o` 且 ( o≠money o≠money) ,做为一名 ACMer QAQ~敏锐的发现可以把 `money` 拆分成若干个数的和（注 ：拆分的数里不能出现 `1`）从而缴纳更少的所得税，当然这也是允许的，做为一名正直，勇敢，又充满正能量的 ACMer，K 决定把这个发现告诉火星情报局，以帮助 K 星完善这一新的法律。

“我发现...” 想想都很酷...，当然 QAQ 若想在世界都在看的火星上面提案是要通过多才多艺的”大家“的考核的，考核如下 ：给出一个人的收入 `money` ，输出在 K 星该人可以缴纳的最少的所得税...为了帮助 QAQ 在火星顺提案你能帮他打下助攻吗?

## 输入 ##

第一行一个数 T T （ 1≤T≤1000 1≤T≤1000）,表示 `T` 组测试数据

接下来 T T 行，每行一个人的收入 `money` （ 2≤money≤1012 2≤money≤1012，注 ：`money` 大部分是 106 106 以内的数）

## 输出 ##

对于每个` money` 输出在 K 星可以缴纳的最少的所得税

## 样例输入 ##

3
    2
    5
    8

## 样例输出 ##

1
    1
    2

## 提示 ##

`2`除自身的最大因子是`1`，输出为`1`

`5`除自身的最大因子是`1`，输出为`1`

`8`可以分成`3+5` ，`3`除自身的最大因子是`1`，`5`除自身的最大因子是`1`，所以输出为`1+1=2`

题解：

用到了哥德巴赫猜想，任意一个大于2的偶数可以分解为两个质数的和，任意一个比5大奇数可以表示成3个素数。

1，当为素数时，直接输出1；

2，当为偶数时，可以分解为两个素数的和，输出2；

3，为奇数（不为质数时），能写成2和一个素数的和，输出2

4，其余情况输出3

代码：

C++ Code

<table style="width:100%; font-family:'Consolas','Courier New'; font-size:12px; vertical-align:text-top; line-height:15px"> 
 <tbody> 
 <tr> 
 <td style="color:#008284; background-color:#e3e3e3; vertical-align:text-top"> 
 <div style="margin:7px; text-align:right; white-space:nowrap">
 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 
 34 
 35 
 36 
 
 </div> </td> 
 <td style="background-color:#008284; padding:1px"> 
 <div style="border:1px #008284 solid"></div> </td> 
 <td style="background-color:rgb(239,239,239); width:100%; vertical-align:text-top"> 
 <div style="margin:7px"> 
 #include&lt;bits/stdc++.h&gt; 
 
 using&nbsp; 
 namespace&nbsp;std; 
 
 int&nbsp;f( 
 long&nbsp; 
 long&nbsp;x) 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;flag&nbsp;=&nbsp; 
 1; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 long&nbsp; 
 long&nbsp;i&nbsp;=&nbsp; 
 2;&nbsp;i&nbsp;&lt;&nbsp;x;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(x&nbsp;%&nbsp;i&nbsp;==&nbsp; 
 0) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;flag&nbsp;=&nbsp; 
 0; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 break; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp;flag; 
 } 
 
 int&nbsp;main() 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;t; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 long&nbsp; 
 long&nbsp;x; 
 &nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d",&nbsp;&amp;t);&nbsp; 
 ///任意一个比2大偶数可以表示成两个素数，任意一个比5大奇数可以表示成3个素数(哥德巴赫猜想) &nbsp;&nbsp;&nbsp;&nbsp; 
 while(t--) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%lld",&nbsp;&amp;x); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(f(x)) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "1\n"); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 else&nbsp; 
 if(x&nbsp;%&nbsp; 
 2&nbsp;==&nbsp; 
 0&nbsp;||&nbsp;f(x&nbsp;-&nbsp; 
 2))&nbsp; 
 ///如果一个数能分成2和一个素数输出2，这个地方有点坑人 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "2\n"); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 else&nbsp; 
 if(x&nbsp;%&nbsp; 
 2&nbsp;==&nbsp; 
 1) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "3\n"); 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 } 
 
 </div> </td> 
 </tr> 
 </tbody> 
</table>

[20170810193853_22503.jpg]: http://acm.hpu.edu.cn/upload/image/20170810/20170810193853_22503.jpg