用筛法求之N内的素数。 （C语言代码）筛求法+优化普通方法

解题思路:

       定义一个数组prime[],赋初值为0，数组下表对应这个数字，通过数组值来判断是否为素数

ex:

    prime[2]==0 表示2为素数  prime[8]==1 表示8不为素数

    根据算术基本定理：任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积

            所以若prime[i]==0,则prime[i*j]==1 即prime[i*j]不为素数

        只要i：2->n 即可构建n以内的质数表

注意事项:
        

        prime[0]=prime[1]=1;    //0 1特殊处理

参考代码:

#include<stdio.h>
int main(){
     int prime[10000]={0};
     int i,j;
     int n;
 
     scanf("%d",&n);
 
     prime[0]=prime[1]=1;
 
     for(i=2;i<n;i++)
         if(prime[i]==0)
               for(j=2;i*j<=n;j++)
                    prime[i*j]=1;
 
     for(i=0;i<n;i++)
          if(prime[i]==0)
               printf("%d\n",i);
 
     return 0;
}

下面是另一种求素数方法，如果可以优化的话在下方留言哦~

#include<stdio.h>
#include<math.h>
 
void judge(int n);
//----------------------------*
int main(void){
      int n,i;
      scanf("%d",&n);
      for(i=2;i<=n;i++)
          if(i%2!=0)        //去偶数
            judge(i);
      return 0;
}
//----------------------------*
void judge(int n){ 
     int i,flag=0;
     double sq;
     sq=sqrt(n);        //减少开根运算
     for( i=2;i<=sq;i++)     //因数都是成对存在的 而且因数对一定是一大一小（除平方根）
       if(n%i==0){
            flag=1;
            break;
           }
     if(flag==0)
         printf("%d\n",n);
}