【数论】质数与约数

发布于 15 天前

一、质数

1.质数概念：

在大于 1 的整数中，如果只包含 1 和本身这两个约数，就被称为质数，或者叫素数。

2.质数的判定——试除法

(1)朴素试除法

遍历从$2$到$n-1$的所有数字，只要其中有$n$的约数，就不符合质数的概念，则返回false。
示例代码：

bool is_Prime(int n){
    if(n < 2) return false;
    for(int i = 2; i <= n - 1; i++){
        if(n % i == 0) {
            return false;
        }
    }
    return true;
}

质数必须大于等于2
时间复杂度为$O(n)$

(2)优化试除法

首先我们先来了解一个性质：如果$d$能够整除$n$，则$\frac{n}{d}$一定也能整除$n$，所以在每次约数的时候，我们就发现了$d$与$\frac{n}{d}$都是成双成对出现的，所以我们只需要枚举较小的那一个就可以了。因此枚举的条件就是$d\leq\frac{n}{d}$，简单化简一下就是$d^{2}\leq n$，$d\leq \sqrt{n}$。因此，我们在循环的时候只需要枚举到$\sqrt{n}$就够了。
示例代码：

bool is_Prime(int n){
    if(n < 2) return false;
    for(int i = 2; i <= n / i; i++){
        if(n % i == 0) {
            return false;
        }
    }
    return true;
}

对于循环的结束条件，如果写成i * i <= n会有溢出的风险
对于循环的结束条件，如果写成i <= sqrt(n)会大大增加时间复杂度，因为每次都要重新取。
时间复杂度为$O(\sqrt{n})$

3.分解质因数

(1)朴素算法

从小到大枚举所有的数，如果发现某个数字$t$可以被整除，那么就循环求有多少个$t$可以被整除，直到无法被整除。
示例代码：

void divide(int n){
    for(int i = 2; i < n; i++){
        if(n % i == 0){
            int s = 0;
            while(n % i == 0){
                n /= i;
                s++;
            }
            cout << i << s << "\n";
        }
    }
}

有读者可能会有疑问：为什么分解质因数枚举的不是质数，而是自然数呢？其实仔细一思考就能得到答案，当我们枚举到每个i的时候，就意味着我们n已经不包含任何从$2$到$i-1$的质因子了，而$i$如果是合数的话，必然包含$2$到$n-1$的质因子一定也是质数了。

(2)优化算法

我们首先了解一个很重要的性质：$n$中最多只包含一个大于$\sqrt{n}$的质因子。怎么证明的呢？假设有两个大于$\sqrt{n}$的质因子，那么相乘一定大于$n$。
所以我们枚举的时候，可以先将所有小于等于$\sqrt{n}$的质因子枚举出来，然后最后如果n>1，说明最后剩下的数字一定是那个大于$\sqrt{n}$

void divide(int n){
    for(int i = 2; i < n / i; i++){
        if(n % i == 0){
            int s = 0;
            while(n % i == 0){
                n /= i;
                s++;
            }
            cout << i << s << "\n";
        }
    }
    if(n > 1) cout << n << "1\n";
    cout << endl;
}

时间复杂度为$O(\sqrt{n})$

例题：AcWing197. 阶乘分解

给定整数NNN，试把阶乘N!N!N! 分解质因数，按照算术基本定理的形式输出分解结果中的pip_ipi 和cic_ici 即可。

输入格式

一个整数NNN。

输出格式

N!N!N! 分解质因数后的结果，共若干行，每行一对pi,cip_i, c_ipi,ci，表示含有picip_i^{c_i}pici 项。按照pip_ipi 从小到大的顺序输出。

数据范围

3≤N≤1063 \leq N \leq 10^63≤N≤106

输入样例：

输出样例：

2 3
3 1
5 1

样例解释

5!=120=23×3×55! = 120 = 2^3 \times 3 \times 55!=120=23×3×5

解题思路

对于这个题目，如果直接暴力求的话肯定会超时，而且long long也放不下。所以我们就思考能不能拆分一下？

首先$n!=1\times 2\times 3\times \dots \times n$，所以我们可以将$1,2,3,\dots ,n$每一项都分解质因数，然后最后合并起来（这里是同底数幂相乘，底数不变指数相加的原理）。来计算一下时间复杂度，单独求每一个数的质因子是$O(\sqrt n)$（最坏情况下），一共有$n$个数需要求，所以时间复杂度为$O(n\sqrt n)$，因为$n=10^6$，所以最多需要$10^9$的时间，显然超时了。

如果调换一下枚举顺序这个题目可能就可以做了。我们先枚举每个质因子，然后再求它的次数是多少。

所以第一步就是筛出$1-10^6$中的所有质数，质数个数通过公式$\frac{n}{\ln n}$可以算出来大概是$50000$个。第二步就是求$p$的次数，那么在$1-n$当中有多少个$p$的倍数呢？显然是$\lfloor \frac{n}{p} \rfloor$。但是有些数可能有多个$p$，于是就有了指数。所以在$1- n$当中有$\lfloor \frac{n}{p^2} \rfloor$个$p^2$的倍数。以此类推，所以$p$的次数一共就是$\lfloor \frac{n}{p} \rfloor + \lfloor \frac{n}{p^2} \rfloor+\lfloor \frac{n}{p^3} \rfloor+\lfloor \frac{n}{p^4} \rfloor+\dots$，直到$p^k>n$为止。那么这样的一个式子，总共大概有$\log_p{n}$。因为$n=10^6$，放缩一下，所以时间复杂度大约为$\log_{2}^{10^1} + \log_{3}^{10^6} + \log_{5}^{10^1} + \dots \leq 5000 \times \log_{2}^{10^6}$，那连$5000$都不到，肯定不会超时了。

代码实现如下所示：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e6 + 10;

int primes[N], cnt;
bool st[N];

void get_primes(int n){
    for(int i = 2; i <= n; i++){
        if(!st[i]) primes[cnt++] = i;
        for(int j = 0; i * primes[j] <= n; j++){
            st[i * primes[j]] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

int main(){
    int n;
    cin >> n;
    get_primes(n);

    for(int i = 0; i < cnt; i++){
        int p = primes[i];
        int s=  0;
        for(int j = n; j; j /= p) s += j / p;
        cout << p << " " << s << endl;
    }
    return 0;
}

4、质数的判定——埃氏筛法

对于每个枚举到的$t$，他的任何倍数就一定是合数而非质数。所以我们可以在每次枚举到质数的时候，标记范围内它的所有倍数，这样就可以节省相当多的时间了。

示例代码：

int primes[N], cnt = 0;
bool st[N];

void get_primes(int n){
    for(int i = 2; i <= n; i++){
        if(!st[i]) primes[cnt ++] = i;

        for(int j = i + i; j <= n; j += i){
            st[j] = true;
        }
    }
}

时间复杂度分析

首先当$i=2$的时候循环了$\frac{n}{2}$次，当$i=3$的时候循环了$\frac{3}{n}$次，以此类推：

2n+3n+4n+......+nn=n(12+13+14+......+1n)∼nln⁡n\frac{2}{n}+\frac{3}{n}+\frac{4}{n}+......+\frac{n}{n}=n(\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+......+\frac{1}{n})\sim {n\ln n}n2+n3+n4+......+nn=n(21+31+41+......+n1)∼nlnn

括号内$\frac{1}{2}+\frac{1}{3}+\dots+\frac{1}{n}$是调和级数$H_n=1+\frac{1}{2}+\frac{1}{3}+\dots+\frac{1}{n}$去掉首项1，即$H_n - 1$；
当$n\to\infty$（$n$趋近于无穷大）时，调和级数的渐近近似为：$H_n \approx \ln n + \gamma$（$\gamma\approx0.577$，是欧拉常数）；
因此括号内部分取极限的渐近结果：$\frac{1}{2}+\frac{1}{3}+\dots+\frac{1}{n} \approx \ln n + \gamma - 1 \sim \ln$

综上所述，大致的时间复杂度就是$O(n\ln n)$

[!TIP] 什么是调和级数？
调和级数是指形如1+12+13+14+…1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \dots1+21+31+41+… 的无穷级数。
虽然每一项越来越小，但这个和会一直增长，当 n 足够大时，它大约等于ln⁡n+0.577\ln n + 0.577lnn+0.577（$\ln n$ 是自然对数）。
对于我们这里的时间复杂度分析，只需要知道：
12+13+⋯+1n\frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n}21+31+⋯+n1 大致和ln⁡n\ln nlnn 差不多大
所以n×(12+13+⋯+1n)n \times (\frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n})n×(21+31+⋯+n1) 大致是nln⁡nn \ln nnlnn

对于刚才的埃氏筛法，我们做一个简单的优化。我们会发现并不是每一个数的倍数全部都要删除，其实只要删除每个质数的倍数就可以了。举个简单例子，比如$p$是质数，那么我们不需要枚举$1～\ p-1$的所有数字，只要枚举这个区间之内的质数就可以了。

示例代码：

int primes[N], cnt = 0;
bool st[N];

void get_primes(int n){
    for(int i = 2; i <= n; i++){
        if(!st[i]){
            primes[cnt ++] = i;
            for(int j = i + i; j <= n; j += i){
                st[j] = true;
            }
        }
    }
}

那么此时再次计算新的时间复杂度。刚才我们算了所有数的调和级数，这里只需要计算$[1, \frac{1}{n}]$中的所有质数的调和级数。

我们先来了解一个质数定理：$[1,n]$中有$\frac{n}{\ln n}$个质数。

所以原式就可以少算$\ln n$倍，最终时间复杂度降低为$O(n\log \log n)$。不过粗略估计来看，与$O(n)$相差无几了。

5.质数的判定——欧拉筛法(线性筛法)

每一个数$n$只会被它的最小质因子筛掉。在筛的时候，从小到大枚举所有质数$primes[j]$。

如果i % primes[j] == 0，那么primes[j]一定是i的最小质因子，primes[j]也一定是$primes[j]*i$的最小质因子。
如果i % primes[j] != 0，那么primes[j]一定小于i的所有质因子，那么primes[j]也一定是$primes[j]*i$的最小质因子。

有读者可能会发出疑问：这个算法是如何保证筛掉所有合数的呢？答案很显然，对于一个合数$x$，假设$pj$是$x$的最小质因子，让$i$枚举到x / pj的时候，那么一定就会在此之前枚举过$pj$，那么一定就已经筛去了$x$。

示例代码：

int primes[N], cnt;
bool st[N];

void get_primes(int n){
    for(int i = 2; i <= n; i++){
        if(!st[i]) primes[cnt++] = i;
        for(int j = 0; primes[j] <= n / i; j++){
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

时间复杂度为$O(n)$.

例题：Acwing 1292. 哥德巴赫猜想

哥德巴赫猜想的内容如下：任意一个大于444 的偶数都可以拆成两个奇素数之和。

例如：

8=3+58=3+58=3+5

20=3+17=7+1320=3+17=7+1320=3+17=7+13

42=5+37=11+31=13+29=19+2342=5+37=11+31=13+29=19+2342=5+37=11+31=13+29=19+23

现在，你的任务是验证所有小于一百万的偶数能否满足哥德巴赫猜想。

输入格式

输入包含多组数据。

每组数据占一行，包含一个偶数nnn。

读入以000 结束。

输出格式

对于每组数据，输出形如n=a+bn = a + bn=a+b，其中a,ba,ba,b 是奇素数。

若有多组满足条件的a,ba,ba,b，输出b−ab-ab−a 最大的一组。

若无解，输出 Goldbach's conjecture is wrong.。

数据范围

输入最多包含500065000650006 组数据。

6≤n<1066\le n<10^66≤n<106

输入样例

输出样例

8 = 3 + 5
20 = 3 + 17
42 = 5 + 37

思路

第一种思路：穷举

我们可以从$3$开始枚举$a$，然后令$b=n-a$，再判断如果$a$和$b$都是质数的话，就符合哥德巴赫猜想。但是我们计算一下时间复杂度，循环$n$次，如果在用线性筛法的话就是$\sqrt{n}$，总共的时间复杂度为$O(n\sqrt{n})$，但是$n$的数据范围达到了$10^6$，计算下来总共为$10^9$，超时了！

第二种思路：预处理

因为数据范围是有限的，所以我们可以将$1-10^6$之间的所有质数都找出来，然后从这些质数当中枚举$a$，然后令$b=n-a$，再利用st[]数组判断是否$a$和$b$都是质数，如果都是的话break即可。

示例代码：

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;

int primes[N], cnt;
bool st[N];

void init(int n){
    for(int i = 2; i <= n; i++){
        if(!st[i]) primes[cnt ++] = i;
        for(int j = 0; i * primes[j] <= n; j++){
            st[i * primes[j]] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

int main(){
    init(N - 1);

    int n;
    while(cin >> n, n){
        for(int i = 1; ; i++){
            int a = primes[i], b = n - a;
            if(!st[b]){
                cout << n << " = " << a << " + " << b << endl;
                break;
            }
        }
    }
    return 0;
}

例题：AcWing 1293. 夏洛克和他的女朋友

夏洛克有了一个新女友（这太不像他了！）。

情人节到了，他想送给女友一些珠宝当做礼物。

他买了nnn 件珠宝，第iii 件的价值是i+1i+1i+1，也就是说，珠宝的价值分别为2,3,…,n+12, 3, \dots, n+12,3,…,n+1。

华生挑战夏洛克，让他给这些珠宝染色，使得一件珠宝的价格是另一件珠宝的价格的质因子时，两件珠宝的颜色不同。

并且，华生要求他使用的颜色数尽可能少。

请帮助夏洛克完成这个简单的任务。

输入格式

只有一行一个整数nnn，表示珠宝件数。

输出格式

第一行一个整数kkk，表示所使用的颜色数；
第二行nnn 个整数，表示第 1 到第nnn 件珠宝被染成的颜色。

若有多种答案，输出任意一种。
请用 1 到kkk 表示你用到的颜色。

数据范围

1≤n≤1051 \le n \le 10^51≤n≤105

输入样例1

输出样例1

2
1 1 2

输入样例2

输出样例2

2
2 1 1 2

解题思路

如果将每个数字看成一个点，有质因数关系的就连上一条边，这个问题就变成了图论问题，但是这样做会非常的麻烦。所以我们就来看一下这个题有没有什么特殊的性质呢？

首先我们的数列中，边必然是从一个质数连接到另一个合数，于是这就抽象成一个二分图的染色问题，所以我们把质数放在一边，合数放在另一边，因此两个集合分别染上两种颜色，因为所有边的点都在两个颜色中，所以就没有任何一条边连接两个颜色相同的点了，本题的答案最多就有两种了。

代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100010;

int primes[N], cnt;
bool st[N];

void get_primes(int n){
    for(int i = 2; i <= n; i++){
        if(!st[i]) primes[cnt ++] = i;
        for(int j = 0; i * primes[j] <= n; j++){
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

int main(){
    int n;
    cin >> n;
    get_primes(n + 1);

    if(n <= 2) cout << 1 << endl;
    else cout << 2 << endl;

    for(int i = 2; i <= n + 1; i++){
        if(!st[i]) cout << 1 << " ";
        else cout << 2 << " ";
    }
    return 0;
}

二、约数

1.试除法求一个数的所有约数

基本思路与试除法求质数类似，也是从小到大判断，如果可以整除就是约数了。

优化也同试除法求质数一样，我们只需要枚举到$\sqrt{n}$就可以了。

示例代码：

int nums[N], cnt;

void devisors(int n){
    cnt = 0;
    for(int i = 1; i <= n / i; i++ ){
        if (n % i == 0){
            nums[cnt ++] = i;
            if (i != n / i) nums[cnt ++] = n / i;
        }
    }
    sort(nums, nums + cnt);
}

[!TIP] 时间复杂度为$O(\sqrt{n})$。

2.约数个数

首先我们知道任意一个数$N$可以拆分成几个质数相乘的形式：$N=p_{1}^{\alpha 1}p{2}^{\alpha 2}p{3}^{\alpha 3}......p{k}^{\alpha k}$。所以$N$的任何一个约数$d$也可以写成几个质数相乘的形式：$d=p1^{\beta_1}p_2^{\beta_2}p_3^{\beta_3}......p_k^{\beta_k}$，此时$\frac{N}{d} = p_1^{\alpha_1-\beta_1} p_2^{\alpha_2-\beta_2} \cdots p_k^{\alpha_k-\beta_k}$必为整数，这要求每一个质因子的指数都非负，即满足$0\leq \beta_i \leq \alpha_i$。

那么对于每个质因子$p_i$，他的指数就有$0、1、2、3、4、...、\alpha_i$共$a_i+1$种情况可选，那么根据分步乘法原理，约数个数就是$(\alpha_1 +1)(\alpha_2 +1)(\alpha_3+1)......(\alpha_k+1)$。

比如N=12=22×31N=12=2^2 \times 3^1N=12=22×31，对于质因子$2$，指数可以选$0/1/2$（共$3$种）；对于质因子333，指数可以选$0/1$（共$2$种）；组合起来：$2^0 \times 3^0=1$、$2^1 \times 3^0=2$、$2^2\times 3^0=4$、$2^0 \times 3^1=3、2^1 \times 3^1=6、2^2 \times 3^1=12$ 。共$3\times 2=6$ 个约数，和公式结果一致。

那么我们就可以直接利用这个定理来求约数的个数了。

例题：AcWing 871. 约数个数

给定$n$个正整数$a_i$，请你输出这些数的乘积的约数个数，答案对$10^9+7$取模。

输入格式

第一行包含整数$n$。

接下来$n$行，每行包含一个整数$a_i$。

输出格式

输出一个整数，表示所给正整数的乘积的约数个数，答案需对$10^9+7$取模。

数据范围

1≤n≤100,1≤ai≤2×1091\leq n\leq100,1\leq a_i\leq2\times10^91≤n≤100,1≤ai≤2×109

输入样例

输出样例

解题思路

既然题目让我们求$a_1\times a_2\times a_3 \times ...... \times a^n$的约数个数，那么就可以先对它进行质因数分解。要分解如此庞大的一个数显然不好做，于是我们就可以逐个分解每个$a_i$为$p_1^{\beta_1}p_2^{\beta_2}...p_k^{\beta_k}$，然后将$n$个数的指数相加就能得到总共的质因数分解。

然后直接套用公式就可以解决，示例代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <unordered_map>

using namespace std;

typedef long long LL;

const int mod = 1e9 + 7;

int main(){
    int n;
    cin >> n;

    unordered_map<int, int> primes;
    while (n --){
        int x;
        cin >> x;
        for(int i = 2; i <= x / i; i++ ){
            while(x % i == 0){
                x /= i;
                primes[i]++;
            }
        }
        if(x > 1) primes[x]++;
    }

    LL res = 1;
    for(auto prime : primes) res = res * (prime.second + 1) % mod;
    cout << res << endl;
    return 0;
}

例题：AcWing1291. 轻拍牛头

今天是贝茜的生日，为了庆祝自己的生日，贝茜邀你来玩一个游戏．

贝茜让$N$头奶牛（编号$1$到$N$）坐成一个圈。除了$1$号与$N$号奶牛外，$i$号奶牛与$i-1$号和$i+1$号奶牛相邻，$N$号奶牛与$1$号奶牛相邻。

农夫约翰用很多纸条装满了一个桶，每一张纸条中包含一个$1$到$1000000$之间的数字。接着每一头奶牛$i$从桶中取出一张纸条，纸条上的数字用$A_i$表示。

所有奶牛都选取完毕后，每头奶牛轮流走上一圈，当走到一头奶牛身旁时，如果自己手中的数字能够被该奶牛手中的数字整除，则拍打该牛的头。

牛们希望你帮助他们确定，每一头奶牛需要拍打的牛的数量。即共有$N$个整数$A_1,A_2,…,A_N$，对于每一个数$A_i$，求其他的数中有多少个是它的约数。

输入格式

第一行包含整数$N$。接下来$N$行，每行包含一个整数$A_i$。

输出格式

共$N$行，第$i$行的数字为第$i$头牛需要拍打的牛的数量。

数据范围

1≤N≤1051 \le N \le 10^51≤N≤105，$1 \le A_i \le 10^6$

输入样例：

输出样例：

解题思路

如果我们按照题意，对于每一个数$i$都去求他的约数，那么至少需要$O(\sqrt n)$的时间复杂度，而数据范围显然不合适。那么我们不妨倒推，我们不求约数，反过来求每个数的倍数，如果数列当中出现了倍数那么就符合要求了。代码如下

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

const int N = 1e6 + 10;
int n;
int a[N], s[N], cnt[N];

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        cnt[a[i]]++;
    }
    for(int i = 1; i < N; i++){
        for(int j = i; j < N; j += i){
            s[j] += cnt[i];
        }
    }
    for(int i = 1; i <= n; i++){
        cout << s[a[i]] - 1 << endl;
    }
    return 0;
}

例题：AcWing1294. 樱花

给定一个整数nnn，求有多少正整数数对(x,y)(x,y)(x,y) 满足$\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}$。

输入格式

一个整数nnn。

输出格式

一个整数，表示满足条件的数对数量。
答案对109+710^9+7109+7 取模。

数据范围

1≤n≤1061 \le n \le 10^61≤n≤106

输入样例

输出样例

解题思路：

已知方程1x+1y=1n!\frac{1}{x} + \frac{1}{y} = \frac{1}{n!}x1+y1=n!1，我们可以化简一下。首先通分得x+yxy=1n!\frac{x + y}{xy} = \frac{1}{n!}xyx+y=n!1，交叉相乘后(x+y)⋅n!=xy(x + y) \cdot n! = xy(x+y)⋅n!=xy。接下来展开并整理含yyy 的项得

x⋅n!+y⋅n!=xy，x⋅n!=xy−y⋅n!，x⋅n!=y(x−n!)x \cdot n! + y \cdot n! = xy，x \cdot n! = xy - y \cdot n!，x \cdot n! = y(x - n!)x⋅n!+y⋅n!=xy，x⋅n!=xy−y⋅n!，x⋅n!=y(x−n!)

最后直接得出y的表达式：

y=x⋅n!x−n!y = \frac{x \cdot n!}{x - n!}y=x−n!x⋅n!

所以这个题目本质上就是问我们$x$有多少种正整数的取值使得$y$是一个整数。那么我们这样看起来还是不好突破，所以再次对式子进行化简：$y=n!+\frac{(n!)^2}{x - n!}$

因为$n!$一定是整数，所以我们只要保证$\frac{(n!)^2}{x - n!}$是整数就可以了。因为$x-n!$一定是正整数，所以这个题目就变成了让我们求$(n!)^2$的约数个数。

怎么求$(n!)^2$的约数个数？这个就可以参见3.分解质因数中的阶乘分解这个题目了，算法思路一模一样。代码如下。

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1e6 + 10, mod = 1e9 + 7;

int primes[N], cnt;
bool st[N];

void get_primes(int n){
    for(int i = 2; i <= n; i++){
        if(!st[i]) primes[cnt++] = i;
        for(int j = 0; i * primes[j] <= n; j ++){
            st[i * primes[j]] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

int main(){
    int n;
    cin >> n;
    get_primes(n);

    int res = 1;
    for(int i = 0; i < cnt; i++){
        int p = primes[i];
        int s = 0;
        for(int j = n; j; j /= p) s += j / p;
        res = (LL)res * (2 * s + 1) % mod;
    }
    cout << res << endl;
    return 0;
}

例题：AcWing198. 反素数

对于任何正整数xxx，其约数的个数记作g(x)g(x)g(x)，例如g(1)=1g(1)=1g(1)=1、$g(6)=4$。

如果某个正整数xxx 满足：对于任意的小于xxx 的正整数iii，都有g(x)>g(i)g(x) > g(i)g(x)>g(i)，则称xxx 为反素数。

例如，整数111，$2$，$4$，$6$ 等都是反素数。

现在给定一个数NNN，请求出不超过NNN 的最大的反素数。

输入格式

一个正整数NNN。

输出格式

一个整数，表示不超过NNN 的最大反素数。

数据范围

1≤N≤2×1091 \le N \le 2 \times 10^91≤N≤2×109

输入样例:

输出样例:

解题思路

本来素数的约数个数非常少，所以本题反过来，约数个数很多的是反素数了。那我们先来想一下，1∼n1\sim n1∼n当中最大的反素数是哪个数？我们知道：所有约数个数最多的数当中，最小的一个数其实也就是我们要找的反素数。并且它后面没有任何一个约数个数严格大于这个反素数。

3.约数之和

若正整数nnn的质因数分解为n=p1a1p2a2…pkakn = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k}n=p1a1p2a2…pkak（p1,p2,…,pkp_1,p_2,\dots,p_kp1,p2,…,pk为互不相同的质数，a1,a2,…,aka_1,a_2,\dots,a_ka1,a2,…,ak为正整数），将它们加起来后因式分解得$n$的所有正约数的和为

S=(p10+p11+p12+⋯+p1a1)(p20+p21+p22+⋯+p2a2)…(pk0+pk1+pk2+⋯+pkak)S = (p_1^0 + p_1^1 + p_1^2 + \dots + p_1^{a_1})(p_2^0 + p_2^1 + p_2^2 + \dots + p_2^{a_2}) \dots (p_k^0 + p_k^1 + p_k^2 + \dots + p_k^{a_k})S=(p10+p11+p12+⋯+p1a1)(p20+p21+p22+⋯+p2a2)…(pk0+pk1+pk2+⋯+pkak)

文章

浏览(14)