米勒拉宾素数检验
今年 1024 程序员节公司搞活动,让我做一次分享。我在分享会上谈及程序优化时,说道优化算法减少时间复杂度的优化往往比优化代码本身更优化。举的一个例子就是检测一个整数是否是素数的问题。
米勒拉宾素数检验法比普通方法有数量级上的性能提高。当时我说道,这个算法的原理其实并不复杂,其证明过程有高中数学知识就可以理解,并不需要多深奥的数学知识。
会后,有同学提出了疑问。他怀疑一个高中生真的能看懂 wikipedia 上的解释 。仔细读了一遍后,我认为,对于中学生来说,难懂的可能只是其中的一些专有术语罢了,那些中学数学课本上没有引入。其内核还是挺好懂的。而且,这篇中文版写的(以及排版)不太好,远没有英文版清晰 。或许只要看英文版就立刻明白了。
我也许可以写一篇没那么多术语,但也不够严谨的解释。