浅谈（C语言）Eratoshenes筛法寻找素数与一般算法

爱拉托塞斯筛法（Eratoshenes筛法）是一种寻找素数的方法，又称平凡除法或厄拉托塞斯（Eratoshenes）筛法。
其是应用定理“设n是正整数，如果对虽有的素数p≤√n,都有p不能整除n,则n一定是素数.”得到的一个寻找素数的确定性方法。下面给出具体描述：
对任意给定的正整数N，要求出所有不超过N的素数。列出N个整数，从中删除不大于√N的所有素数P1,P2,P3,……,Pk的倍数（除素数P1,P2,P3,……,Pk外）。具体的是依次删除，
            P1的倍数：2·P1,3·P1,4·P1,……,[N/P1]·P1；
            P2的倍数：2·P2,3·P2,4·P2,……,[N/P2]·P1；
            P3的倍数：2·P3,3·P3,4·P3,……,[N/P3]·P1；
                    …………
            Pk的倍数：2·Pk,3·Pk,4·Pk,……,[N/Pk]·P1.
余下的整数（不包括1）就是所有求的不超过N的素数（[x]表示小于或等于x的最大整数）。

#include <stdio.h> #include <stdlib.h>
#include <math.h>
#include <conio.h>
#include <time.h>
void main( )
{
    long max,k ,k1,i,j,m,ad,sd;
    sd=0;
    ad=0;
    long *a;
    long start,end;
    printf("请输入一个数:");
    scanf("%ld",&max);                    //输入一个数
    start = clock();
    k=(long)sqrt((float)max);
    printf("开平方后取整k=%ld",k);
    if(NULL==(a=(long*)malloc(sizeof(long)*max)))
    {
        printf("memmery error!\n");
        exit(1);
    }
    for(i=0;i<max;i++){                    //初始化数组a,记录1~max
        a[i]=i+1;
    }
    long *s;                            //s记录K内的素数
    if(NULL==(s=(long*)malloc(sizeof(long)*k)))
    {
        printf("memmery error!\n");
        exit(1);
    }
    for(i=0;i<k;i++){                    //初始化数组s
        s[i]=0;
    }

    for(m=2;m<=k;m++){                    //求k内的素数
        k1=int(sqrt(double(m)));
        for(i=2;i<=k1;i++){                //while(m%i && i<=k1)
            if(m%i==0)                    //  i++;
                break;                    //
        }
        if(i>k1){
            
            s[sd]=m;
            sd++;                        //sd即为k内素数的个数
        }
    }
    printf("\n%ld内的素数有：\n",k);
    for(i=0;i<sd;i++){                
        if(s[i]!=0)
            printf("%ld\t",s[i]);
    }
    
    for(i=2;i<max;i++){                    //爱拉托塞斯筛选
        for(m=0;m<sd;m++){
            for(j=2;j<=(max/s[m]);j++){
                if(a[i]==(j*s[m]))
                    a[i]=0;
            }
        }
    }
    
    end = clock();
    printf("\n不超过%ld的素数有：\n",max);
    for(i=1;i<max;i++){                
        if(a[i]!=0)
            printf("%ld\t",a[i]);
    }
    printf("用时%ld毫秒\n",end-start);
    getchar();
    getchar();
}

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <conio.h>
#include <time.h>
void main()
{
    long max,k,i,m;
    long start,end;
    printf("请输入一个数:");
    scanf("%ld",&max);                    //输入一个数
    start = clock();
    printf("\n%ld内的素数有：\n",max);
    for(m=2;m<=max;m++){                    //求k内的素数
        k=int(sqrt(double(m)));
        for(i=2;i<=k;i++){                //while(m%i && i<=k)
            if(m%i==0)                    //  i++;
                break;                    //
        }
        if(i>k){
            
            printf("%ld\t",m);
                    
        }
    }
    end = clock();
    
    printf("用时%ld毫秒\n",end-start);
    getchar();
    getchar();
}

#C/C++##笔经#