素数相关

• 欧拉筛法
• 用数组v[i]来记录这个数的最小质因子
• 依次考虑2-n这些数
• 如果v[i] = i，表示这个数为素数，把这个数存起来
• 否则，扫描所有小于等于v[i]的素数，令v[ip] = p,表示ip这个数的最小质因子是p，被p给筛掉了，这样每个合数就只会被筛一次

//时间复杂度为O(n)
int cnt= 0；
int prime[100010];
int v[100010];
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];
  //筛取这个合数
  }
}

• 素数的性质

  1.1~n范围内的素数个数大约为log(n)个
  2.素数的分布整体上来说随着数的增大而越来越稀疏，但存在局部的紧密。

• 算数基本定理
  何一个大于1的自然数 ，如果N不为质数，都可以唯一分解成有限个质数的乘积 ，这里
  这里均为质数，其诸指数是正整数。
  由这个定理易得一个数的正因子个数：
  全体正因子之和：

-例题
给定两个整数L,R,求[L,R]内相邻两个质数的最大差值,(L,R<=2^31)(R-L<=1e6).
首先考虑打表，但2e9范围内的素数太多，数组存不下。然后我们考虑暴力去判断区间内的每一个数是否是素数，使用朴素做法，时间复杂度为O(n√n),无法承受。
考虑优化朴素做法，判断一个数是否为质数，实际上只需要判断这个数能否被小于等于√n的素数整除，而不需要把每一个数去枚举一遍，这样只要把小于等于√2e9的素数打一个表，这样复杂度就是O(n+nlogn)，是可以承受的。