计算质数的多种优化算法

这是一个程序员的自我修养,一个学术者的自我探索,一个大神的养成之道。

什么是质数?

质数,又称素数,有无限个。质数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数的数称为质数。

一般我们求质数时都会去计算小于某一个数N的质数而不会不加限定,现在我们以求小于N的质数来说一说优化方式。在我们求质数的过程中一般会用到两种方法试除法和筛选法两种。

试除法

①判断小于N的数X是否是质数,就是从2一直尝试到X-1,这种做法效率最差,并不可取。

②如果X是质数,那么它如果不能被小于X/2的数整除即可,这样算法效率提高一些

③除了2以外,所有的质数都只能是奇数,所以我们可以将数X先试除2,然后尝试从3一直到X/2的所有奇数

④其实判断一个数是否是质数,只需判断一个数能不能被除了1之外小于x的数整除即可,

⑤最后,我们可以利用前面求出来的质数来判断,我们只需判断X能不能被小于x的质数整除即可,这样效率会更高。

筛选法

①定义一个容器,将数据放入容器中,然后遍历其中的数据,将是合数的数据删除,最后剩余的就是质数了

②我们可以定义一个布尔类型的数组容器,将其中的值都赋值为true,在筛选的过程中将不是质数的数作为数组的下标将对应元素的值改为false,最后取出值为true的元素的下标即可

③构造定长的byte数组,数组的每个byte存储8个布尔值,这样性能有了些许提高。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 第一章数和数的运算 一概念 (一)整数 1整数的意义 自然数和0都是整数。 2自然数 我们在数物体的时候,用来表示...
    meychang阅读 7,641评论 0 5
  • 小学奥数其实很简单,以下是这六个部分的知识点! 1 第一部分(知识点1-6) 2、年龄问题的三个基本特征: ①两个...
    小一哥阅读 5,158评论 0 3
  • 小升初的过程中,竞赛成绩能起到相当大的作用,谈到竞赛就离不开奥数。以下是小学奥数题知识点大汇总: 1.和差倍问题 ...
    沪江中小幼阅读 4,818评论 0 7
  • 夜拥深更夜怨重,堆雪海棠梦,落梧桐。晓风萧萧说穷情,想不尽,心关锁千重。 冷月勾倦帘,无心理情怀,来晨风。寒浓揉破...
    易安阅读 2,555评论 0 1
  • 慧慧 (一) 有一次在街边,看见一个女子拉着一个3、4岁大的孩子,路过一位穿着破旧、头发蓬乱跪在地上乞讨的小女孩儿...
    慧慧huiskite阅读 1,703评论 2 0