51Nod－1106－质数检测

给出N个正整数，检测每个数是否为质数。如果是，输出”Yes”，否则输出”No”。
Input
第1行：一个数N，表示正整数的数量。(1 <= N <= 1000)
第2 - N + 1行：每行1个数(2 <= S[i] <= 10^9)
Output
输出共N行，每行为 Yes 或 No。
Input示例
5
2
3
4
5
6
Output示例
Yes
Yes
No
Yes
No

遇见这道题，我第一感觉又是个坑，不搞些小手段一定会超时，但是怎么才能不超时呢？传统的因子检测法是肯定行不通的，结果一查吓我一跳，又是费马检测，又是AKS质数测试，一堆看得不是太懂的概念性东西，充斥着荧屏，硬着头皮看了一天也只是懵懵懂懂，然后我再一次念叨那句话，作为一个程序员，如果你给我数学公式的话，那还不如给我代码去学习。

于是我就上网找到了一个不错的代码，仔细一看，这个代码并没有用上边说的那两个特别复杂的检测思路，而是利用了传统的因子检测，但是它优化了很多，利用质因子检测的原理，成功的节省了大量的时间，效率有显著的提升，鉴于个人能力有限（数学真的挂了），我暂时先用这种质因数的检测来AC吧，毕竟舍本逐末的事太消耗时间，还不一定能够弄透彻……

#include <stdio.h>


#define _MAX 5000
int a[_MAX + 1] = {
  1,1};
int p[_MAX + 1];
int main()
{
    int num = 0;
    for(int i = 2; i <= _MAX; i++)
    {
        if(!a[i])
            p[num++] = i;
        for(int j = 0; j < num && i * p[j] <= _MAX; j++)
        {
            a[i * p[j]] = 1;
            if(!(i % p[j]))
                break;
        }
    }
    int t, n;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        if(n <= _MAX)
        {
            if(!a[n])
            {
                printf("Yes\n");
            }
            else
            {
                printf("No\n");
            }
        }
        else
        {
            int ok = 1;
            for(int i = 0; i < num; i++)
            {
                if(n % p[i] == 0)
                {
                    ok = 0;
                }
            }
            if(ok)
            {
                printf("Yes\n");
            }
            else
            {
                printf("No\n");
            }
        }
    }
    return 0;
}