prime

什么是质数？

质数是指只能被1和自身整除的正整数。2、3、5、7等都是质数，4、6、8等都不是质数。

质数的性质所有大于1的整数都可以表示为若干个质数相乘的形式，这就是素因子分解定理。具体来说，如果一个整数n可以表示为p1^a1*p2^a2*...*pk^ak（中p1,p2,...,pk均为不同的质数），那么我们称p1,p2,...,pk为n的素因子，ai为n在pi下的指数。

根据这个定理，我们知道任何一个合数（大于1且不是质数）都可以分解成若干个质因子之积。而一个给定的正整数n，如果它不能被小于或等于根号n的正整数整除，则它一定是素数。

如何快速判断一个数字是否为质数？

暴力枚举法：即给定的数字n，从2到(n-1)依次枚举每个数字i，并判断是否能够被n整除。如果存在一个i使得n%i==0，则说明n不是质数；否则说明n是质数。

试除法：给定的数字n，从2到(n/2)依次枚举每个数字i，并判断是否能够被n整除。如果存在一个i使得n%i==0，则说明n不是质数；否则说明n是质数。试除法相比暴力枚举法更加高效一些，但较大的数字仍然会很慢。

米勒-拉宾素性测试：算法基于费马小定理：如果p为素数，则任意a(0<a

2)的自然数组成序列，并将中所有能被当前处理到的最小素子筛掉（即标记为非素因子），直至遍历完全序列，剩下未被筛掉的即均为素因子。算法时间复杂度约为O(N*loglog(N))。

线性筛法：算法类似埃氏筛法，但在标记非素因子时采用了线性方式避免重复标记导致时间浪费一次遍历中同时完成了筛选和计算每个合成数字最小素因子等信息保存，并无需额外存储空间时间和空间两方面都优化了传统埃氏筛方法。