北航计算机机试08素数

输入一个整数，要求输出所有从1到这个整数之间个位为1的素数，如果没有则输出-1（30分）

#include<stdio.h>
#include<stdlib.h>

int main()
{
    int max;
    int len,i,j;
    int flag;
    while(scanf("%d",&max)!=EOF)
    {
        flag=0;
        len=0;
        max%2==0?len=max/2:len=(max+1)/2;
        int *a=NULL;
        a=(int*)malloc(len*sizeof(int));
        for(i=0,j=3;i<len-1;i++,j+=2)
        {
            a[i]=j;
        }
        for(i=0;i<len-1;i++)
        {
            if(a[i]!=0)
            {
                for(j=a[i];a[i]*j<=max;j+=2)//for是先判断还是先do
                {
                    int m=a[i]*j;
                    int k=(m-1)/2;
                    if(k<len)
                    {
                    a[k-1]=0;
                    }
                }
            }
            if(a[i]%10==1){ printf("%d\n",a[i]);flag=1;}
        }
        if(flag==0) printf("-1\n");
        free(a);
    }
    return 0;
}

思路：
1. 我这里用的是经典筛法求素数，直接百度就知道原理，在最一般化的筛法求素数中，从1开始一直到我们所给的范围，很多数比如，6，15会被删除两次，那么多删除一次就会增加时间复杂度
2. 改进的筛法求素数是只存储范围内的奇数，从奇数3开始，再按本身的奇数倍递增去筛除非素数
3. 注意边界值