埃氏筛法(c语言)

  • 思路:我们可以建立一个大一点的数组,用来存储每个数是否是素数(素数用1表示,非素数用0表示),我们每找到一个素数就把他们的倍数变成非素数。
  • 思路非常简单接下来就直接上代码吧
//这个是主要步骤的实现代码
for(int i = 2;  i * i <= MAXSIZE; i++)
    {
        if(nums[i])
        {
            for(int j = i + i; j < MAXSIZE; j += i)
            {
                nums[j] = 0;
            }
        }
    }
  • 接下来让我们进行一些测试
#include <stdio.h>
#include <stdlib.h>
#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;
}

埃氏筛法(c语言)

上一篇:C++队列——纸牌问题


下一篇:Java用数组实现《数据结构》中栈的出入 。