备战蓝桥杯---数学基础1
质数的性质：
1.n>3,n与n+1必然有一个不是质数。
2.质数有无穷多个：
如果有限个，那么他们的乘积+1必然也是质数，矛盾。
3.存在任意长的一段连续的数都是合数。
我们令长度为n,构造a=(n+1)!,则(a+2)%2=0,(a+3)%3=0......(a+n+1)%(n+1)=0.
4.n以内的素数个数随n增大趋于logn
5.从不大于n的自然数随机选一个，他是素数的概率约1/lnn;
6.素数随着n增大愈加稀疏
7.a>1,(a,2a]中必然存在一个素数。
8。n与n+2都为素数情况很多。
9.任意>2的正偶数都可以写成两个素数的和（哥德巴赫猜想）
素数的判定：
1.埃氏筛：
从2开始，是质数的话就划掉他的倍数，显然，我们每一次枚举的数只要不被划掉就是素数。
！一个小优化：
每个合数都可表示：a*b,a是素数，如果a>b,那么他就没必要用a再一次筛，因此，在用a筛时，我们从a^2开始。
我们可以进一步优化，使其不会重新筛。
2.欧拉筛：
比如30=2*3*5，我们如何保证它只被5筛一次呢？
于是我们引进.欧拉筛，先看代码：
for(int i=2;i<=n;i++){
if(v[i]==0){
v[i]=i;
prime[++cnt]=i;}
for(int j=1;j<=cnt;j++){
if(prime[j]>v[i]||i*prime[j]>n) break;
b[i*prime[j]]=prime[j];}}
下面分析一下它的思路：
对于一个合数a1*a2*a3(a1<a2<a3并都是素数)，为了保证不重复计算，我们规定用一个数去筛时，乘它的数要小于等于他的最小质因子，我们先得到a1，在a2筛的时候筛了a1*a2,并标记它的最小质因子为a1,在求a3时我们用它筛了a1*a3,a2*a3，而在a2*a3时，a1<a2，因此它就把a1*a2*a3给筛了。
概括一下，就是我们先得出最大的质因子，然后再*第二大的，依次类推，递减的*质因子。
而一个合数的质因子肯定有非递减的顺序，这也就保证了不重复性。（如果说埃氏筛的筛法类似于求排列，那么欧拉筛则是求组合）
还有一点，如何保证v[i]=i的就是素数。
我们可以想对于一个合数a1*a2*a3，在a2*a3那就筛了，显然a1>1，因此v[i]=i的就是素数。