Eratosthenes筛选法求解质数

问题说明:

除了自身之外，无法被其它整数整除的数称之为质数，要求质数很简单，但如何快速的求出质数则一直是程式设计人员与数学家努力的课题，在这边介绍一个着名的 Eratosthenes求质数方法。

解法:

首先知道这个问题可以使用回圈来求解，将一个指定的数除以所有小于它的数，若可以
整除就不是质数，然而如何减少回圈的检查次数？如何求出小于N的所有质数？

我们先来看一个丧心病狂的低效率的解决方式:

//检验质数
bool checkZS(int a)
{
    for (int i = 2;i < a;i++)
    {
        if (0 == a%i)
        {
            return false;
        }
    }
    return true;
}

首先我们写一个检验质数的函数,下面我们在主函数调用:

int n = 99999;
    clock_t start,end;//用于计时
    start = clock()    ;
    for(int i = 1;i <= n;i++)
    {
        if (checkZS(i))
        {
            cout<<i<<" ";
        }
    }
    end = clock();
    cout<<"\n总共花费了"<<(long double)(end - start)/CLK_TCK<<"秒"<<endl;

好了,让我们看下在99999以内的质数算出来的运行结果:

时间花费了17秒,太慢了;下面我们想想怎样来改进算法!

首先知道这个问题可以使用回圈来求解，将一个指定的数除以所有小于它的数，若可以整除就不是质数，然而如何减少回圈的检查次数？如何求出小于N的所有质数？
首先假设要检查的数是N好了，则事实上只要检查至N的开根号就可以了，道理很简单，假设A*B = N，如果A大于N的开根号，则事实上在小于A之前的检查就可以先检查到这个数可以整除N。不过在程式中使用开根号会精确度的问题，所以可以使用 i*i <= N进行检查，且执行更快。
再来假设有一个筛子存放1～N，例如：
2 3 4 5 6 7 8 9 10 11 12 ........N
先将2的倍数筛去：
2 3 5 7 9 11 13........N
再将3的倍数筛去：
2 3 5 7 11 13 17 19........N
再来将5的倍数筛去，再来将7的质数筛去，再来将11的倍数筛去........，如此进行到最后留下的数就都是质数，这就是Eratosthenes筛选方法（Eratosthenes Sieve Method）

检查的次数还可以再减少，事实上，只要检查6n+1与6n+5就可以了，也就是直接跳过2与3的倍
数，使得程式中的if的检查动作可以减少。

下面我们上代码:

/*
问题:
除了自身之外，无法被其它整数整除的数称之为质数，要求质数很简单，但如何快速的
求出质数则一直是程式设计人员与数学家努力的课题， 在这边介绍一个着名的 Eratosthenes求质
数方法。
2013/7/18
张威
*/
#include <iostream>
#include <time.h>
using namespace std;

#define n 99999

int main()
{
    int a[n+1];//建立一个数组,使a[i] == i,这样通过筛选,将非质数所在位置置0
    for (int i = 0;i <= n;i++)
    {
        a[i] = i;
    }
    clock_t start,end;//用于计时
    start = clock()    ;

    //每次进行筛选的数,进行优化,实际上只要筛选到 N开放就行
    for (int i = 2;i*i <= n;)
    {
        //从i处开始筛选(比i小的肯定不能被i整除)
        for (int j = i;j <= n;j++)
        {
            //通过while循环.跳过中间置0区域
            while(0 == a[j] && j <= n)
                {
                    j++;
                }
            //假如a[j]能被i整除而且不相等(也就是说不是本身),就把这个位置数值置为0
            if (0 == a[j]%i && i != a[j])
            {
                a[j] = 0;
            }
        }
        //i的步进值优化,即跳过2或3的倍数,每次递增数加大
        if((i-1)%6 == 0)
            i += 4;
        else if((i-5)%6 == 0)
        {
            i += 2;
        }
        else
        {
            i++;
        }
    }
    end = clock();
    for(int i = 2;i <= n;i++)
    {
        if (a[i] != 0)
        {
            cout<<a[i]<<" ";
        }
    }
    cout<<"\n总共花费了"<<(long double)(end - start)/CLK_TCK<<"秒"<<endl;
    return 1;
}

Eratostheness

上面标出了在减少算法中循环次数的优化方面所进行的修改,下面是运行结果:

两者之间的差距的话.......不说了,自己写的东西和这些算法相比就是渣渣!

下面上示例上面的代码:

#include <stdio.h>
#include <stdlib.h>
#define N 1000
int main(void) {
int i, j;
int prime[N+1];
for(i = 2; i <= N;i++)
prime[i] = 1;
for(i = 2; i*i <= N;i++) { // 这边可以改进
if(prime[i] == 1) {
for(j = 2*i; j <= N;j++) {
if(j % i == 0)
prime[j] = 0;
}
}
}
for(i = 2; i < N;i++) {
if(prime[i] == 1) {
printf("%4d ", i);
if(i % 16 == 0)
printf("\n");
}
}
printf("\n");
return 0;
}

示例代码

可以看到其实还是上面自己写的在示例的基础上还是做了些改善的!

Eratosthenes筛选法求解质数

推荐阅读