C语言中素数的高速判断和筛法创建

C语言中素数的快速判断和筛法创建。

素数是一类很有用的数，至今为止，没有任何人发现素数的分布规律，也没有人能用一个公式计算出所有的素数。但素数的判断和创建是有法可循的。

常用方法一：优化的枚举法（效率O(n*sqrt(n)))，按照素数的定义从2-枚举到SQRT（N）。方法简单易懂，这个用于判断可以，但是创建的话时间过长。

int isprime(int n)
{
    for (int i=2;i<=sqrt(n);i++)
    {
        if (n%i==0)
            return 0;
    }
    return 1;
}

常用方法二：筛法。（效率O(n))

筛法的意思遵循一个原则,素数i的倍数一定不是素数。

（以下为转载）

一个简单的筛素数的过程：n=30。

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

   

    第 1 步过后2 4 ... 28 30这15个单元被标成false,其余为true。

    第 2 步开始：

     i=3;  由于prime[3]=true, 把prime[6], [9], [12], [15], [18], [21], [24], [27], [30]标为false.

     i=4;  由于prime[4]=false,不在继续筛法步骤。

     i=5;  由于prime[5]=true, 把prime[10],[15],[20],[25],[30]标为false.

     i=6>sqrt(30)算法结束。

    第 3 步把prime[]值为true的下标输出来：

     for(i=2; i<=30; i++)

     if(prime[i]) printf("%d ",i);

    结果是 2 3 5 7 11 13 17 19 23 29

筛法还可以优化，于是有了方法三：优化筛法。

把所有偶数都去掉，时间复杂度进一步降低。

模板：

int prime(int a[],int n)
{
    int i,j,k,x,num,*b;
    n++;
    n/=2;
    b=(int *)malloc(sizeof(int)*(n+1)*2);
    a[0]=2;
    a[1]=3;
    num=2;
    for (i=1;i<=2*n;i++)
        b[i]=0;
    for (i=3;i<=n;i+=3)
        for (j=0;j<2;j++)
        {
            x=2*(i+j)-1;
            while (b[x]==0)
            {
                a[num++]=x;
                for (k=x;k<=2*n;k+=x)
                    b[k]=1;
            }
        }
    return num;
}

关于素数，还有一些好玩的性质：

1、哥德巴赫猜想，著名的素数问题，任何一个大于4的偶数都可以拆成2个素数。

2、孪生素数问题，差为2的素数有无穷对。

3、反证法的第一个试刀案例，欧几里得证明了世界上没有最大的素数，这玩意没有最大只有更大

4、目前人类（计算机？）算出来的最大素数为2^43112609-1，一个723W+位的数字.....