数论——素数

向右看齐 2021-11-01 06:16 362阅读 0赞

转自：[http://www.cnblogs.com/linyujun/p/5198832.html][http_www.cnblogs.com_linyujun_p_5198832.html]

整合：[https://blog.csdn.net/x\_i\_y\_u\_e/article/details/46365549][https_blog.csdn.net_x_i_y_u_e_article_details_46365549]

整合：[https://blog.csdn.net/qq\_43332305/article/details/82959066][https_blog.csdn.net_qq_43332305_article_details_82959066]

# 说明 #

1.  π(x) ，素数分布函数，为小于等于 x 的素数的个数。
2.  当 x 趋于 无穷大时，π(x) 与 x / lnx等价。
3.  当 x 趋于 无穷大时，1~x 中所有素数的倒数和与 $\\ln \\ln x$ 等价。
4.  factor(x) 表示x的因子个数，比如 factor(6) = 4。

## 素数 ##

### 定义 ###

除了1和它本身以外不再有其他的因数的数。也叫质数。

### 素数判定 ###

根据素数的定义判定（复杂度$O(\\sqrt\{n\})$）

#### 代码如下 ####

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 //素数
    2 inline bool isPrime(const LL x) {
    3     if (x <= 1)return false;
    4     for (LL i = 2; i * i <= x; i++)if (x % i == 0)return false;
    5     return true;
    6 }

### 埃拉托斯特尼筛法 ###

原理：如果找到一个质数，那么这个质数的倍数都不是质数。

这个方法能在 $O(n \\ln \\ln n)$ 的时间复杂度内筛选出 1~n 中的所有素数。示例图如下：

![埃拉托色尼筛法图示][E5_9F_83_E6_8B_89_E6_89_98_E8_89_B2_E5_B0_BC_E7_AD_9B_E6_B3_95_E5_9B_BE_E7_A4_BA.gif]

#### 复杂度说明如下 ####

设 pi 为 1~n 中第 i 个素数。

对于每一个 pi，都要筛去 n / pi 个数，因此，筛选行为总数为 n \* (1/p1 \+ 1/p2 \+……+ 1/pπ(n)) ，等价于 $n\\ln \\ln n$。

#### 代码如下 ####

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 bool primes[maxN];
     2 inline void Eratosthenes(){
     3     For(i, 2, maxN) primes[i] = true;//先全部初始化为质数 
     4     For(i, 2, maxN) {
     5         if(primes[i]){
         //如果i是质数 
     6             for(int j = 2 * i; j < maxN; j += i){
         //从i的两倍开始的所有倍数 
     7                 primes[j] = false; 
     8             }
     9         }
    10     }
    11 }

这个代码还能进一步优化，一个合数如果有因数，那么必定是成对存在，也就是筛子只用判断其中一个因数就可以了，比如15=3\*5，在3的时候已经把15给筛掉了，何必去循环到5呢？循环到根号 n 即可。

第二层循环中，j 可以从 i \* i开始，因为 i \* (i - 1)， i \* (i - 2) 等等这些数必然已经被比 i 小的质数筛掉了。

#### 代码如下（优化后） ####

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 bool primes[maxN];
     2 inline void Eratosthenes(){
     3     For(i, 2, maxN) primes[i] = true;//先全部初始化为质数 
     4     for(int i = 2; i * i < maxN; ++i) {
     5         if(primes[i]){
         //如果i是质数 
     6             //从i * i开始的所有倍数
     7             for(int j = i * i; j < maxN; j += i){
     8                 primes[j] = false; 
     9             }
    10         }
    11     }
    12 }

### 线性筛法（**欧拉筛法**） ###

以空间换时间的方法，一个数只会经过一次，能把时间复杂度降为 O(n)。

#### 代码如下 ####

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 const int N = 1000;
     2 bool isPrime[N + 7];//isPrime[i]表示i是不是质数 
     3 VI primes;//primes用来存质数 
     4 inline void Euler(){
     5     For(i, 2, N) isPrime[i] = true;//初始化为质数 
     6     For(i, 2, N) {
     7         if(isPrime[i]) primes.PB(i);//把质数存起来 
     8         for(int j = 0; j < primes.size() && i * primes[j] <= N; ++j) {
     9             isPrime[i * primes[j]] = false;
    10             if(i % primes[j] == 0) break;//保证每个合数被它最小的质因数筛去 
    11         }
    12     }    
    13 }

## 算术基本定理 ##

### 定义 ###

任何一个大于1的自然数 N，如果N不为质数，那么N可以唯一分解成有限个质数的乘积。当然 N 为质数的时候就是本身，没必要分解。

设 N 的质因子为：p1， p2， ……，pπ(N)。（从小到大排）

设对应质因子个数为：e1， e2， ……，eπ(N)。

则定义的公式表示为：$$N = \\prod\_\{i=1\}^\{π(N)\} \{p\_i\}^\{e\_i\}$$

## 约数个数定理 ##

$$factor(N) = \\prod\_\{i=1\}^\{π(N)\} \{e\_i + 1\}$$

## 反素数 ##

### 定义 ###

对$\{\\forall\_\{0 < i < n\}\}$ ，都有 factor(n) > factor(i)，称 n 为反素数。

### 性质 ###

1.  一个反素数的质因子必然是从2开始连续的质数。
2.  分解质因数后对应质因子的个数满足：e1 >= e2 >=……>= eπ(n)。

### 求不大于 n 的最大反素数代码 ###

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 LL n;
     2 // ans = （最大反素数，相应因子数） 
     3 PLL ans;
     4 int primes[] = {
         2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};
     5 
     6 // x 表示当前处理到第 x 个质数
     7 // ret为当前选择下的质数乘积 
     8 // pcnt 为 1~x-1 个质数中，每个质数选择数量+1的乘积 
     9 // limit 表示第x个质数选则的上限 
    10 // cnt表示第 x 个质数已经选了多少个 
    11 inline void dfs(int x = 0, LL ret = 1, LL pcnt = 1, int limit = inf, int cnt = 0) {
    12     if(ret > n || limit < cnt) return;
    13     LL tmp = pcnt * (cnt + 1);
    14     if(ans.sd < tmp || ans.sd == tmp && ans.ft > ret) ans = MP(ret, tmp);
    15     
    16     if(n / ret >= primes[x])dfs(x, ret * primes[x], pcnt, limit, cnt + 1); // 选 primes[x]
    17     if(cnt) dfs(x + 1, ret, tmp, cnt, 0); // 不选 primes[x]
    18 }

转载于:https://www.cnblogs.com/zaq19970105/p/10799564.html

[http_www.cnblogs.com_linyujun_p_5198832.html]: http://www.cnblogs.com/linyujun/p/5198832.html
[https_blog.csdn.net_x_i_y_u_e_article_details_46365549]: https://blog.csdn.net/x_i_y_u_e/article/details/46365549
[https_blog.csdn.net_qq_43332305_article_details_82959066]: https://blog.csdn.net/qq_43332305/article/details/82959066
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211101/d0a66bf591154b0e81c5b45f034f5717.png
[E5_9F_83_E6_8B_89_E6_89_98_E8_89_B2_E5_B0_BC_E7_AD_9B_E6_B3_95_E5_9B_BE_E7_A4_BA.gif]: /images/20211101/7efc6c987c374bdb8e239b179df3da26.png