筛选法求素数

我们都知道求一个数是不是素数的方法是十分简单的，但是当你判断一个数字集合里面都有哪些素数的时候，纯暴力法就会显得效率十分低下，这时候就需要用技巧筛掉明显不是素数的数字，剩下的再采用暴力直接求解，那么那些明显不是素数呢？首先偶数全不是素数，其次一个素数的倍数也不是素数，那么筛掉这两种情况剩余的一定是素数（反证法可证明），程序如下：

int min,max;
    int t;
    int i,j,k;
    int flag[10000] = {0};
    int num[10000];
    num[2] = 1;
    num[1] = 0;
    printf("请输入数字的区间范围:");
    scanf("%d,%d",&min,&max);
    if(min > max)
    {
        t =min;
        min = max;
        max = t;
    }
    //4以后的偶数全不是素数
    for(i = 4; i<= max; i+=2)
    {
        flag[i] = 1;
    }
    //从3开始计算
    for(i = 3 ;i <= max;i++)
    {
        if(flag[i])
        {
            num[i] = num[i - 1];
            continue;
        }
        else
        {
            num[i] = num[i - 1] + 1;
            //素数的倍数全不是素数
            for(k = i ; k <= max; k+=i)
            {
                flag[k] = 1;
            }
        }
    }
    printf("在%d到%d之间，一共有%d个素数",min,max,num[max] - num[min]);
    system("pause");
    return 0;