用筛法求之N内的素数。 （C语言代码）

解题思路:

明确一个条件，任何合数都能表示成一系列素数的积。

然后利用了每个合数必有一个最小素因子，每个合数仅被它的最小素因子筛去正好一次。

所以为线性时间

参考代码:

#include<stdio.h>
int primes(int n);    
//其中primes（）函数是用来排素数的函数
int prime[100000]={0};                        
//用来存储素数的数组，初始化全部为0
int p[100000]={0};                               
//用来间接验算是不是素数的数组，初始化全部为0
int main()
{
    int number,i,size;         
//其中number为用户输入的数，size为prime（）传回来的在0~number以内有多少个素数
    scanf("%d",&number);
    size=primes(number);           
//传回多少个素数
    for(i=0;i<size;i++)
    {
        printf("%d\n",prime[i]);    
//输出
    }
    return 0;
}
int primes(int n)                    
{
    int top=0,i,j;                         
//定义top为prime[]中已有的素数个数
    for(i=2;i<=n;i++)
    {
        if(!p[i])                             
//判断p[i]有没有被修改过，如果没有被修改过，就还是0，
// 则对应此时的i为素数，否则就是1，将可以判断其肯定不是素数.
    {
        prime[top++]=i;               
        //输入素数
    }
    for(j=0;j<top&&i*prime[j]<=n;j++)
    {
        p[i*prime[j]]=1; 
//这个是欧拉筛选的精髓，当前的值与前面已经出现的素数相乘，其合数肯定不是素数，为其
//赋值1，这样在前面!p[i]判断的时候就可以跳过了
        if(i%prime[j]==0)
//关键 prime数组 中的素数是递增的,当 i 能整除 prime[j]，
//那么 i*prime[j+1] 这个合数肯定被 prime[j] 乘以某个数筛掉。
               break; 
// 因为i中含有prime[j], prime[j] 比 prime[j+1] 小。接下去的素数同理。所以不用筛下去了。  
            
    }
    }
    return top;
}

希望对大家有帮助，有bug或者是问题，请在下面评论区留言