Chinaunix首页 | 论坛 | 博客
  • 博客访问: 995583
  • 博文数量: 135
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1780
  • 用 户 组: 普通用户
  • 注册时间: 2016-12-21 22:26
个人简介

90后空巢老码农

文章分类

全部博文(135)

文章存档

2020年(32)

2019年(54)

2018年(47)

2017年(1)

我的朋友

分类: C/C++

2018-01-10 23:25:11

最近在看一些数据结构和算法方面的书,对于有些东西,觉得有必要自己整理记录一下,就又回到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数组来确定哪个是素数了。

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

阅读(1476) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~