埃氏筛法（c语言）

• 思路：我们可以建立一个大一点的数组，用来存储每个数是否是素数（素数用1表示，非素数用0表示），我们最开始假定2以后的数都是素数，每找到一个素数就把他们的倍数变成非素数。
• 思路非常简单接下来就直接上代码吧

//这个是主要步骤的实现代码
for(int i = 2;  i * i <= MAXSIZE; i++)
    {
        if(nums[i])
        {
            for(int j = i + i; j < MAXSIZE; j += i)
            {
                nums[j] = 0;
            }
        }
    }

• 接下来让我们进行一些测试

#include 
#include 
#define MAXSIZE 100000005
int nums[MAXSIZE]={0, 0};

int main()
{
    int n;
    for(int i = 2; i < MAXSIZE; i++)
    {
         nums[i] = 1;
    }
    for(int i = 2;  i * i <= MAXSIZE; i++)
    {
        if(nums[i])
        {
            for(int j = i + i; j < MAXSIZE; j += i)
            {
                nums[j] = 0;
            }
        }
    }
    printf("输入几组判断数据");
    scanf("%d", &n);
    while(n--)
    {
        int s;
        scanf("%d", &s);
        if(nums[s])
            printf("是素数n");
        else
            printf("不是素数n");
    }
    return 0;
}