获取小于N的素数 优化筛选法的C++实现

孪生素数(间隔为2的相邻素数)的相关定理与推论

P1: 当 N 不小于 6 且 N-1 和 N+1 为 孪生素数, 则 N 一定是 6的倍数

T1:当 N 不小于 1 且 N=6x-1 或 N=6x+1 不是素数, 那么 N 一定不是 2和 3的倍数

P2:当N 不小于 5 时,若 N 为素数,那么N mod 6 =1或N mod 6 = 5

T2: 一个大于5的数有且只有整除6余数是 1 或者 5 才有可能是素数

一个数 整除6 的余数 可能是 1,2,3,4,5 但是 余数 为2,3,4的情况下 肯定是合数

T3: 一个大于3的素数,其与下一个素数之间的间隔是偶数

具体代码如下

/* *************************************************************** * NAME: sp.cpp * DESC: * AUTHOR: Liu Dongguo([e-mail]) * VERSION: 1.0 * CREATE: 2015-04-10 19:53:36 * LUTIME: 2015-04-10 20:00:53 * * Copyright (c) 2007 - 2015 Abodu.com,Inc. All Rights Reserved * *************************************************************** */
#include <stdio.h>
#include <math.h>
#include <string.h>

#define CH_NO 'n'
#define CH_OTH 'o'
#define CH_YES 'y'

char* GetPrimesLessN(int nSize) //nSize是上限值
{
    int fLen= nSize;
    char* flag=new char[fLen];
    memset(flag,CH_YES,fLen);
    flag[0]=flag[1]=CH_OTH; //排除0和1
    for(int i=2;i*i<nSize;)
    {
        for(int j=i*i;j<nSize;j+=i)
        {
            flag[j]=CH_NO;
        }
        //探测下一个素数距离当前素数的可能步长
        if(i==2) //2特殊:到3 的距离就是1
        {
            i++;
            continue;
        }
        i+=2; 
        while(flag[i]==CH_NO) //修改此处直到找到下一个素数为止
        {
            i+=2; 
        }
    }
    return flag;
}

int main(int argc, char *argv[])
{
    int fLen= 10000;
    char* fls=GetPrimesLessN(fLen);
    int i= 0, cnt= 0;
    while(i<=fLen)
    {
        if(fls[i]==CH_YES) //内容是'y'的数组元素下标为素数
        {
            printf( "%3d ",i );
                cnt++;
            if(!(cnt%10))
                printf("\n");
        }
        i++;
    }
    printf( "\nSummary: 0-%d has %d prime numbers.\n", fLen, cnt );

    delete(fls); //释放由GetPrimesLessN内部分配的内存
    return 0;

} /* end main */