筛选法求素数

一、一般求素数的方法：一个数n的因子不会超过sqrt(n)。

代码如下：C/C++代码

#include<stdio.h>
#include<math.h>
voidprime(int n)
{
    int i=2;
    while(i<=sqrt(n))
        if(n%i++==0) return;
    printf("%d ",n);
}
intmain()
{
    int i,m,n;
    scanf("%d%d",&m,&n);
    for(i=m;i<=n;i++)
        prime(i);
    return 0;
}

二、筛选素数的方法不是直接判断一个数是不是素数，而是将不是素数的数全部去除，剩余的就是素数了。

1.如果区间包含1，首先将1标记为非素数。

2.从下一个最小的素数a开始，将该素数的倍数（2a，3a，……，ka）全部标记为非素数。

3.从a的后面找下一个最小的素数，重复2操作。

4.重复2,3操作，直到所有元素都筛选完为止。

例如：筛选1到25之间的素数

①按部就班地按上面的4步做，第一步，将1标记为非素数；第二步，找下一个素数a=2，标记2的倍数4,6,8，……，22,24；第三步，重复第二步，这时a=3，标记6,9，……，21,24；第四步，重复第二步第三步，a=5，a=7，a=11,a=13,a=17,a=19,a=23

步骤如下图所示：

相应的代码如下：C/C++代码

#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
#define N 8099999
bool prime[N];
__int64 num[N],count;
void getprime()
{
    __int64 i,j;
    memset(prime,0,sizeof(prime));
    count=0;
    for(i=2;i<=N;i++)
    {
        if(prime[i]==0)
        {
            num[count++]=i;
        }
        for(j=2*i;j<=N;j+=i)
            if(prime[j]!=1)
               prime[j]=1;
    }
}
int main()
{
    __int64 i;
    getprime();
    for(i=0;i<count;i++)
        printf("%I64d ",num[i]);
    return 0;
}

②当我们再看看上面的步骤时，我们发现有些非素数不只标记一次，例如6这个数字，当a=2和3时都被标记，那么如果我们只标记一次，就会节约一定的时间，这样我们就可以优化程序。同时我们还可以发现，当a=2时，我们只需从2x2=4开始标记2的倍数；当a=3时，上面是从6开始标记的，其实我们只需从3x3=9开始标记3的倍数即可（因为6已经在a=2时被标记）；当a=5时，上面是从10开始标记的，其实我们只需从5x5=25开始标记5的倍数即可（因为10、20已经在a=2时被标记，15已经在a=3时被标记）。

过程如下图所示：

根据刚刚的方法，我们可以有以下代码：

#include<stdio.h>
#include<string.h>
//N代表要求[0,N]区间的上限
#define N 5000000
//数组prime用来标记非素数
bool prime[N];
//数组p储存素数，count记录素数的个数
__int64 p[N],count=0;
//筛选素数的函数
void getprime()
{
    __int64 i,j;
    memset(prime,0,sizeof(prime));
    for(i=2;i<=N;i++)
	{
		if(prime[i]==0)
		{
            p[count++]=i;
            for(j=i*i;j<=N;j+=i)
                prime[j]=1;
        }
	}
}
int main()
{
    getprime();
    //输出区间[0,N]之间的所有素数
    for(int i=2;i<count;i++)
        printf("%I64d ",p[i]);
    return 0;
}

//N代表要求[0,N]区间的上限
#define N 5000000
//数组prime用来标记非素数
bool prime[N];
//数组p储存素数，count记录素数的个数
__int64 p[N],count=0;
//筛选素数的函数
void getprime()
{
    __int64 i,j;
    memset(prime,0,sizeof(prime));
    for(i=2;i<=N;i++)
	{
		if(prime[i]==0)
		{
            p[count++]=i;
            for(j=i*i;j<=N;j+=i)
                prime[j]=1;
        }
	}
}