/*
素数
时间限制:500MS  内存限制:1000K
Description
数学对于计算机学是很重要的，大一的高数就曾经（或即将）令一批又一批人饮恨。这里就是一个数学问题，当然，它不需要用到高深的高数知识。
给出n（1<=n<=100000），问1到n之间有几个素数。
输入格式
第1行，1个整数T（T<=100000），表示共有T组测试数据
第2---第T+1行，每行1个整数，表示测试数据n
输出格式
对于每个测试数据，输出1行，每行1个数，表示1到n之间的素数个数
输入样例
5
1
2
100
1000
5000
输出样例
0
1
25
168
669
 */
#include <stdio.h>

main()
{
    int n,i,a[100000],j,m,s=0;
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
    for(i=0;i<n;i++)
    {
        for(j=2,s=0;j<=a[i];j++)
        {
            for(m=2;m<=j/2;m++)
            {
                if(j%m==0)
                    goto L;   
            }
            s++;
            L:;
        }
        printf("%d\n",s);
    }
}

判断素数n，只需要1到sqrt(n)为除数

素数判定--朴素方法
对于正数n，用i∈ [2，n]或i∈ [2,n/2]或i∈ [2,√𝒏]依次试除，若n/i不等于0在整个区间成立，则n是素数。

我用了几种方法都是显示超时了，哪位大神帮我优化一下

楼主是acmer？求题号。。。我有一种思路不知道行不行。。先求出100000以内（因为T<=100000）全部素数。。。之后根据输入值去数就是了。。求的时候不要全部去除。。就直接除小于这个数的素数。。。比如5，那么判断是否是素数的时候，就只要除以2和3。4因为能够被2整除，那么能被4整除的都能被2整除了。。。这样的话就可以剪掉大部分计算。。。时间复杂度应该很小了。。。。。特意申请的一个账号回复的。。看到就回复个吧。

#include"stdio.h"
#include"math.h"
main()
{
    int n,i,a[100000],j,m,s=0;
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
    for(i=0;i<n;i++)
    {
        for(j=2,s=0;j<=sqrt(a[i]);j++)
        {
            for(m=2;m<=sqrt(j);m++)
            {
                if(j%m==0)
                    goto L;   
            }
            s++;
            L:;
        }
        printf("%d\n",s);
    }
}

其实这个方法我在网上有看到，自己试了一下，但是还是超时