Description

请判断给出的n是不是素数？

Input

输入每一行包含一个正整数n，n<=231-1;      （2的三十一次方）

Output

如果n是素数请输出“YES”，否则输出“NO”；

Sample Input

4
5
6

Sample Output

NO
YES
NO

#include <stdio.h>

 
int main()
{
    int n,i,flag;
    while(scanf("%d",&n)!=EOF)
    {
        if(n<=0)
            break;
        flag=1;
        for(i=2;i<=n/2;i++)
            if(n%i==0)
                flag=0;
        if(flag==1&&n>1)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}
/**************************************************************
    Problem: 1012
    User: 201501020151
    Language: C
    Result: Time Limit Exceed
****************************************************************/

结果上面写着，时间超限，我真是不懂了，完全就是按老师的思路写的怎么会不对呢？
http://acm.zcmu.这是网址。

[此贴子已经被作者于2016-2-4 03:08编辑过]

首先，这个算法本身就不快
其次，你这个算法还可以优化
for(i=2;i<=n/2;i++)，其中 n/2 可优化为 根号n
对于2的倍数，没必要每个都除一下