笔记 - 质数

题目

• 洛谷: 质数距离 典
  \(大意\) 求[L, R] 中 相邻俩质数的最大差. (\(1≤L 且 \(R-L≤10^6\))
  AC代码

• AcWing197: 阶乘分解 典
  \(大意\) 将 N! 质因数分解 (\(1≤N≤10^6\))
  AC代码

算法

判定

• 试除法 : 若N为合数, 则存在T|N, 且\(2≤T≤\sqrt{N}\)   　\(O(\sqrt{N})\)
  可以利用 质数均是 6n+1 or 6n+5 来进行 以6为增量的快进

  bool isprime(int x){
      if(x<=1) return false;
      if(x==2 || x==3) return true;   // 注意特判
      if(x%6!=1&&x%6!=5) return false;
  
      for(int i=5; (ll)i*i<=x; i+=6)
          if(x%i==0 || x%(i+2)==0) return false;
      return true;
  }
  

• Miller_Robbin算法^[1]

筛选

• Eratosthenes筛法　任意整数x的倍数均不是质数.
  可优化: 算法过程中, 小于x2已经被标记过了　　\(O(NloglogN)\)

  void get_prime(int n){
  	REP(i, 1, n) v[i] = 0;
  	REP(i, 2, n){
  		if(v[i]) continue;
  		printf("%d\n", i);
  		REP(j, i, n/i) v[i*j] = 1;		// 小于 x*x 已经被筛过了
  	}
  }
  

• 欧拉线性筛　从大到小累积质因子, 每个数只筛一次　\(O(N)\)

  void get_prime(int n){
      REP(i, 2, n){
    	  if(!pv[i]){
    		  pv[i] = i;			// pv[i]: i 的最小质因子
    		  prime[++pm] = i; 
    	  }
    	  REP(j, 1, pm){
    		  int p=prime[j];
    		  if(p>pv[i] or p>n/i) break;
    		  pv[p*i] = p;
    	  }
      }
  }
  

质因数分解

• 试除法: 注意要特判 试除完后n是否大于1　\(O(\sqrt{N})\)
  void divide(int n){
  for(int i=2; i*i<=n; ++i){
  if(n%i==0){
  p[++m] = i, c[m] = 0; // m: 质因子个数; c[m]: 第 m 个质因子的指数
  while(n%i == 0) n/=i, c[m]++;
  }
  }
  if(n>1) p[++m]=n, c[m]=1; // 要考虑 n 为质数的情况
  }

• Pollard's Rho