题目描述
众所周知，密码安全是互联网时代人们最为关心的事情之一。而 RSA 公钥加密算法是目前最有影响力和最常用的公钥加密算法，它能够抵抗到目前为止已知的绝大多数密码攻击。
其实 RSA 公钥加密算法的原理并不复杂，它基于一个十分简单的数论事实：将两个大素数相乘十分容易，而想要对其乘积进行质因数分解却极其困难，因此可以将乘积公开作为加密密钥。
所以 RSA 算法很重要的一个过程就是得到两个大素数相乘结果。
wchhlbt 和 Lazy_sheep 想要模拟一下 RSA 算法的加密过程。现在 wchhlbt拿到了 Lazy_sheep 提供的一份素数相乘的结果，但是 Lazy_sheep 因为别的事情计算的并不认真。 所以 wchhlbt 希望你来帮他判断这些数据的正确性。
这个题一上来的思路就是循环数组中的每个数a[i]，找到两个数相乘并且都是素数时输出yes。 这个题还是要稍微思考如何尽可能减少循环。 两个素数的寻找时当然可以分别用个for，这就O（n的三次方的）了暂且不说内部还需不需要for循环。 首先外层遍历必不可少。我们应尽可能考虑一下这两个乘积的关系。
eg：A=b*c b首先从2开始遍历（因为要找素数，2是素数中最小的。） c应该是多少？b=2时，c最大为也只能为 A/b 。所以没必要再要一层循环遍历c b=3时，c最大为也只能为A/b；。。。等等以此类推。 （具体详细：请看懂代码的流程，看懂每个语句的功能，然后试数，最后自己敲一遍！！！）
# include <stdio.h> # include <stdbool.h> //包含了bool函数 # include <math.h> //要用sqrt函数优化素数算法 bool deal(int ); //函数声明 bool prime(int ); int main(void) { int t; scanf("%d",&t); int a[t]; int i; for(i=0;i<t;i++) //输入 { scanf("%d",&a[i]); } for(i=0;i<t;i++) //依次遍历 { if( deal(a[i]) ) printf("YES\n"); else printf("NO\n"); } return 0; } bool deal(int num) //找到两个素数乘积为num { int i; for(i=2;i<=(num/i);i++) //i=2,与之相乘的最大数就是num/2，另外一个数不可能比这个还大，所以只需要判断到num/i就可以；其余自己试数 { if(prime(i) && (0==num%i) && prime(num/i)) //如果i是素数，num/i不是小数（循环中/号回默认取整）的同时是素数,则可以返回true return true; } return false; //当一次for循环中一次if都没进去的话，证明num没有两个素数相乘的结果，返回false } bool prime(int num) //普通判断素数方法（素数：只能被1和它本身整除） { int i=2; for(;i<=sqrt(num);i++) { if(0 == (num%i)) { return false; } } return true; }说明： 当时刚开始有思路写代码时比较混乱，最后一直超时，除了代码本身没有优化外，很重要的一点是，我刚开始的时候把所有代码都写到了main中。这是非常不好的，对于“高内聚、低耦合”来说，我的老师告诉我：应当分函数。
函数应该有多短小才足够？《代码整洁之道》一书中给出的答案是：20行封顶最佳。
