素数算法

最近在看一些数据结构和算法方面的书，对于有些东西，觉得有必要自己整理记录一下，就又回到CU了，然后就发现自己上一次（也就是第一次）写博客已经是一年以前了，好好反省，以后争取定时整理、记录自己所学。
言归正传，今天这篇文章想讲讲关于素数的算法。
闲话少说，先看个定义：只有1和它本身两个因数的自然数。
根据这个定义的话，我们可以出示第一个比较“想当然”的算法。
1.原始算法

bool is_prime_orig(int n)
{
    for(int i = 2; i <n;i++)
        if( n % i == 0)
            return false;
    return true;
}

但是，这样看起来有点傻乎乎的，不太符合我们理工男“懒”的特质，于是乎根据数学常理，我们发现貌似不用从2遍历到n，只需要遍历到n的平发根就可以了，于是乎，就有了下面的两个“比较简单的方法”
2. 源于平方根的两个算法：

bool is_prime_sqrt(int n)
{
    int root = sqrt(n);/*注意，这里要引用头文件math.h*/
    for(int i =2;i<=root;i++)
        if(n%i==0)
            return false;
    return true;
}

bool is_prime_mult(int n)
{
    for(int i = 2; i*i <=n;i++)
        if( n % i == 0)
            return false;
    return true;
}

第二种算法还是有改进之处的，想想看，是不是大部分合数（非质数）的因子当中都有2,3,5呢？
我们可以根据这个，先判断一个数是否为2,3,5倍数的数，再去运用第二种算法来判断，时间会快很多
3.排除2,3,5倍数算法

bool is_prime_excl(int n)
{
    if(n%2==0||n%3==0||n%5==0)
        return false;
    for(int i = 7; i*i <=n;i++)/*这里要从7开始哈*/
        if( n % i == 0)
            return false;
    return true;
}

有了第三种算法的过渡，本文的最后一种算法也就呼之而出了，大体思想就是先开一个比较大的布尔数组is_prime[N+2], 记录每一个数字是否为素数，将其下标从2到N的元素都初始化为true；然后设置一个哨兵trav从2开始遍历到N，每一次遍历时，将在N范围内的下标为trav整数倍的is_prime数组中元素置为false，遍历结束之前，找到下一个is_prime为真的元素下标，将其值赋给trav，一直遍历到结束。
4.筛选算法

#define N 1000
bool is_prime[N+2];
void filter_primes()
{
    for(int i = 1; i<=N;i++)
        is_prime[i]=true;
    is_prime[1] = false;
    is_prime[N+1] = true;
    int trav = 2;
    while(trav <= N)
    {
        for(int i=2*trav;i<=N;i=i+trav)
            is_prime[i]=false;
        do{
            trav++;
        }while(!is_prime[trav]);
    }
}

最后就可以遍历整个is_prime数组来确定哪个是素数了。

本文就介绍到这里了，欢迎大家提出宝贵意见。
今后一定勤更新！！！
今后一定勤更新！！！
今后一定勤更新！！！