OI中质数也是一片神奇的天地QAQ
质数：设p≠0/1，如果p除了1和p以外，没有其它的约数，那我们称p为质数。
合数：设p≠0/1，如果p除了1和p以外，有其它的约数，那我们称p为合数。
注意：0和1既不是质数也不是合数。
质数的分布定理：我们设π(x）为不大于x的质数的个数，π(x）≈x/Inx;(调和级数）
在OI中我们常常要判断一个数是不是质数，或是一个区间内部哪些数是质数，这里我们引入几种方法。
一，试除法（常用于判断一个数是否是质数）
从定义出发，我们枚举除了1和p以外所有可能是它的因子，若某个因子能把它整除，那么这个数就是一
个合数，否则是一个质数，注意我们枚举范围到√n即可，原因很显然的嘛
1 inline bool pd(int x) 2 { 3 if(x<=1) return false; 4 for(int i=2;i*i<=x;i++) 5 if(x%i==0) return false; 6 return true; 7 }
二，质数筛法（常用语判断一个区间内部哪些数是质数）
筛法顾名思义就是通过筛选确定哪些数。
筛法都运用了一个定理即质数的倍数一定不是质数，这也是很显然的，因为1不是质数，所以如果某个数是
某个质数的倍数，那么这个数就有了别的因子，通过这个定理能筛选出区间中所有质数。
1，埃氏筛（是由古希腊数学家埃....记不住提出的）
和定理几乎一样，就是用在这个区间里的质数，去筛掉所有它能筛掉的合数，就可以。
1 inline void ai_shai(int n,bool prime) 2 { 3 memset(prime,true,sizeof(prime));//先默认全部都是质数 4 prime[1]=prime[0]=false; 5 for(int i=2;i<=n;i++) 6 { 7 if(prime[i]) 8 { 9 is_prime[++cnt]=i; 10 for(int j=2;j*i<=n;j++) 11 prime[i*j]=true; 12 } 13 } 14 }
埃氏筛的复杂度是O(nloglogn),应该说可以应付大部分情况了，但仍有可以优化的空间，举个栗子，
12这个合数会被2筛掉一遍，又会被3筛掉一遍，所以造成了时间上的冗余，所以我们可以优化一下，
让所有数，都由它的最小质因子，即（约数是质数的里最小的那一个）筛掉，这样可以去掉冗余，
复杂度为O(n)，是一种线性筛法，名为欧拉筛。
2，欧拉筛
主要思想：所有数都由最小质因子筛去。
1 inline void ou_shai(int n,int cnt,int prime[],int p[]) 2 { 3 for(int i=2;i<=n;i++) 4 { 5 if(p[i]==0) prime[++cnt]=i,p[i]=i; 6 for(int j=1;j<=cnt;j++) 7 { 8 if(i*prime[j]>n||prime[j]>p[i]) break; 9 prime[i*prime[j]]=prime[j];//代表i*prime[j]是由prime[j]这个最小质因子筛掉的 10 } 11 } 12 }
至于别的筛法，NOIP考好以后再补充吧，这些对于NOIP够用了。
关于质数还有个奇妙的东西就是质因数分解。
质因数分解定理：任何一个大于1的正整数都能分解成有限个质数的乘积。
方法：从最小的质数开始除，直到不整除了之后换下一个质数，那我们需要判断哪些数是质数，哪些数
不是质数吗，不用的，因为既然最小的质数都没法整除，它的倍数一定没发整除（合数）。
1 inline void factorize(int x,int p[],int mi[]) 2 { 3 for(int i=2;i<=x;i++) 4 { 5 if(x%i==0) 6 { 7 p[++cnt]=i; 8 while(x%i==0) 9 { 10 x/=i; 11 mi[i]++; 12 } 13 } 14 } 15 if(x>1) 16 { 17 p[++cnt]=x; 18 mi[x]++; 19 } 20 }