素数算法

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

点击(此处)折叠或打开

1. bool is_prime_orig(int n)
   
2. {
   
3.     for(int i = 2; i <n;i++)
   
4.         if( n % i == 0)
   
5.             return false;
   
6.     return true;
   
7. }

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

点击(此处)折叠或打开

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

点击(此处)折叠或打开

1. bool is_prime_mult(int n)
   
2. {
   
3.     for(int i = 2; i*i <=n;i++)
   
4.         if( n % i == 0)
   
5.             return false;
   
6.     return true;
   
7. }

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

点击(此处)折叠或打开

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

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

点击(此处)折叠或打开

1. #define N 1000
   
2. bool is_prime[N+2];
   
3. void filter_primes()
   
4. {
   
5.     for(int i = 1; i<=N;i++)
   
6.         is_prime[i]=true;
   
7.     is_prime[1] = false;
   
8.     is_prime[N+1] = true;
   
9.     int trav = 2;
   
10.     while(trav <= N)
    
11.     {
    
12.         for(int i=2*trav;i<=N;i=i+trav)
    
13.             is_prime[i]=false;
    
14.         do{
    
15.             trav++;
    
16.         }while(!is_prime[trav]);
    
17.     }
    
18. }

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

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