数学专题1 - 素数筛（2）

C++素数练习目录

1. 素数基础

1.1 了解什么是素数及其基本性质

素数(质数)是指在大于1的自然数中,除了1和它本身以外,不能被其他自然数整除的数。换句话说,如果一个数 n n n 只有两个因数:1和 n n n 本身,那么 n n n 就是一个素数。

素数有以下基本性质:

1. 2是最小的素数,也是唯一的偶数素数。

2. 素数的分布是不规则的,但总体上素数的数量随着数值的增大而减少。

3. 任何一个大于1的自然数,要么本身就是素数,要么可以写成素数的乘积。这就是算术基本定理。

4. 素数的和与积仍可能是合数。例如,2和3都是素数,但它们的和5和积6都是合数。

5. 如果 p p p 是素数,且 p p p 不能整除 a a a,那么 a p − 1 ≡ 1 ( m o d p ) a^{p-1} \equiv 1 \pmod{p} ap−1≡1(modp)。这就是费马小定理。

6. 素数在密码学和计算机科学中有着重要的应用,例如RSA加密算法就是基于大素数的难分解性设计的。

1.2 判断素数的常用方法

1.2.1 试除法（记忆）

试除法是最直观、最基本的判断素数的方法。对于一个数 n n n,我们可以从2开始,逐个尝试去除以小于等于 n \sqrt{n} n ​ 的每一个整数,如果都无法整除,则 n n n 是素数,否则 n n n 是合数。

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

1.2.2 埃拉托斯特尼筛法（记忆）

埃拉托斯特尼筛法（Sieve of Eratosthenes）是一种高效的求素数的方法。它的基本思想是,从2开始,将每个素数的倍数标记为合数,最后剩下的未被标记的数就是素数。

const int N = 1e6 + 5;
bool isPrime[N];

void sieve() {
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i < N; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j < N; j += i) {
                isPrime[j] = false;
            }
        }
    }
}

1.2.3 米勒-拉宾素性测试（超纲）

米勒-拉宾素性测试（Miller-Rabin Primality Test）是一种概率性算法,用于快速判断一个大数是否为素数。它的基本思想是基于费马小定理和二次探测定理,通过随机选取若干个数进行测试,可以以很高的概率判断一个数是否为素数。

typedef long long ll;

ll qpow(ll a, ll n, ll mod) {
    ll res = 1;
    while (n) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

bool millerRabin(ll n, int times) {
    if (n == 2 || n == 3) return true;
    if (n < 2 || n % 2 == 0) return false;
    
    ll u = n - 1;
    int t = 0;
    while (u % 2 == 0) {
        u /= 2;
        t++;
    }
    
    for (int i = 0; i < times; i++) {
        ll a = rand() % (n - 2) + 2;
        ll x = qpow(a, u, n);
        for (int j = 0; j < t; j++) {
            ll y = x * x % n;
            if (y == 1 && x != 1 && x != n - 1) return false;
            x = y;
        }
        if (x != 1) return false;
    }
    return true;
}

这些方法各有优缺点。试除法简单直观但效率较低;埃拉托斯特尼筛法可以快速求出一定范围内的所有素数,但需要额外的空间;米勒-拉宾素性测试可以快速判断大数是否为素数,但是是一种概率性算法,存在一定的误判可能。在实际应用中,可以根据具体问题选择合适的判断素数的方法。

2.1 判断一个数是否为素数

题目描述

给定一个正整数 n n n,判断它是否为素数。

输入格式

一个正整数 n n n ( 1 ≤ n ≤ 1 0 18 ) (1 \leq n \leq 10^{18}) (1≤n≤1018)。

输出格式

如果 n n n 是素数,输出 Yes,否则输出 No。

示例

输入:

17

输出:

Yes

输入:

24

输出:

No

解答

我们可以使用试除法来判断一个数是否为素数。对于给定的正整数 n n n,我们从 2 2 2 到 n \sqrt{n} n ​ 枚举所有可能的因数,如果 n n n 能被任意一个数整除,则 n n n 不是素数,否则 n n n 是素数。

以下是C++代码实现:

#include <iostream>
#include <cmath>
using namespace std;

typedef long long ll;

bool isPrime(ll n) {
    if (n < 2) return false;
    for (ll i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    ll n;
    cin >> n;
    if (isPrime(n)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

在上述代码中,我们定义了一个 isPrime 函数,用于判断一个数是否为素数。在主函数中,我们读入一个正整数 n n n,然后调用 isPrime 函数判断 n n n 是否为素数,并输出相应的结果。

需要注意的是,由于题目中给定的数可能很大,所以我们使用了 long long 类型来存储输入的数。

时间复杂度: O ( n ) O(\sqrt{n}) O(n ​)。
空间复杂度: O ( 1 ) O(1) O(1)。

这是一种简单直观的判断素数的方法,对于较小的数可以快速判断。但是对于大数,可以考虑使用更高效的算法,如米勒-拉宾素性测试等。

2.2 求一个区间内的所有素数

题目描述

给定一个区间 [ L , R ] [L,R] [L,R],求出该区间内所有的素数。

输入格式

两个正整数 L L L 和 R R R,表示区间的左右端点。 ( 1 ≤ L ≤ R ≤ 1 0 6 ) (1 \leq L \leq R \leq 10^6) (1≤L≤R≤106)

输出格式

输出该区间内所有的素数,每行输出一个素数。如果区间内没有素数,则输出 No prime number。

示例

输入:

2 20

输出:

2
3
5
7
11
13
17
19

输入:

15 15

输出:

No prime number

解答

我们可以使用埃拉托斯特尼筛法来求出一个区间内的所有素数。以下是使用C++实现的代码:

#include <iostream>
#include <vector>
using namespace std;

vector<int> findPrimesInRange(int start, int end) {
    vector<bool> isPrime(end + 1, true);
    vector<int> primes;
    for (int p = 2; p * p <= end; p++) {
        if (isPrime[p]) {
            for (int i = p * p; i <= end; i += p) {
                isPrime[i] = false;
            }
        }
    }
    for (int i = max(start, 2); i <= end; i++) {
        if (isPrime[i]) {
            primes.push_back(i);
        }
    }
    return primes;
}

int main() {
    int L, R;
    cin >> L >> R;
    vector<int> primes = findPrimesInRange(L, R);
    if (primes.empty()) {
        cout << "No prime number" << endl;
    } else {
        for (int prime : primes) {
            cout << prime << endl;
        }
    }
    return 0;
}

代码解释:

1. 定义 findPrimesInRange 函数,接受两个参数 start 和 end,表示要查找素数的区间范围。
2. 创建一个布尔数组 isPrime,初始时假设所有数都是素数,即将数组元素都设为 true。
3. 从 2 2 2 开始,遍历到 e n d \sqrt{end} end ​,对于每个素数 p p p,将其倍数标记为合数。
4. 遍历区间 [ s t a r t , e n d ] [start, end] [start,end] 内的所有数,将值为 true 的数加入到素数数组 primes 中。
5. 返回素数数组 primes。
6. 在主函数中,读入区间的左右端点 L L L 和 R R R,调用 findPrimesInRange 函数求出区间内的所有素数。
7. 如果素数数组为空,则输出 No prime number,否则将素数逐个输出。

时间复杂度: O ( R log ⁡ log ⁡ R ) O(R \log \log R) O(RloglogR)。
空间复杂度: O ( R ) O(R) O(R)。

这个方法是求区间内素数的一种常用方法,代码实现简单,效率也较高。需要注意的是,在标记合数时,我们从 p 2 p^2 p2 开始标记,而不是从 2 p 2p 2p 开始,这样可以保证所有的合数都被正确标记,而不会遗漏任何合数。

2.3 求第n个素数

题目描述

给定一个正整数 n n n,求第 n n n 个素数。

输入格式

一个正整数 n n n。 ( 1 ≤ n ≤ 1 0 5 ) (1 \leq n \leq 10^5) (1≤n≤105)

输出格式

输出第 n n n 个素数。

示例

输入:

10

输出:

29

输入:

1

输出:

2

解答

为了求第 n n n 个素数,我们可以使用埃拉托斯特尼筛法生成素数表,然后直接取第 n n n 个素数即可。以下是使用C++实现的代码:

#include <iostream>
#include <vector>
using namespace std;

const int N = 1e6 + 5;
bool isPrime[N];
vector<int> primes;

void sieve() {
    fill(isPrime, isPrime + N, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i < N; i++) {
        if (isPrime[i]) {
            primes.push_back(i);
            for (int j = i * i; j < N; j += i) {
                isPrime[j] = false;
            }
        }
    }
}

int main() {
    sieve();
    int n;
    cin >> n;
    cout << primes[n - 1] << endl;
    return 0;
}

代码解释:

1. 定义一个布尔数组 isPrime,初始时假设所有数都是素数,即将数组元素都设为 true。
2. 定义一个整数数组 primes,用于存储生成的素数。
3. 实现 sieve 函数,使用埃拉托斯特尼筛法生成素数表。
   • 从 2 2 2 开始,遍历到 N − 1 N-1 N−1,对于每个素数 i i i,将其倍数标记为合数。
   • 将每个素数加入到 primes 数组中。
4. 在主函数中,调用 sieve 函数生成素数表。
5. 读入正整数 n n n,直接输出 primes 数组中的第 n − 1 n-1 n−1 个元素,即为第 n n n 个素数。

时间复杂度: O ( N log ⁡ log ⁡ N ) O(N \log \log N) O(NloglogN),其中 N N N 是预处理的上限。
空间复杂度: O ( N ) O(N) O(N)。

这个方法的关键是预处理出素数表,然后可以在 O ( 1 ) O(1) O(1) 的时间内得到第 n n n 个素数。预处理的过程使用了埃拉托斯特尼筛法,时间复杂度为 O ( N log ⁡ log ⁡ N ) O(N \log \log N) O(NloglogN)。

需要注意的是,预处理的上限 N N N 需要足够大,以确保能够生成第 n n n 个素数。根据题目给定的范围,我们可以将上限设置为 1 0 6 10^6 106,这样可以保证生成的素数个数足够多。

如果 n n n 的范围更大,可以考虑使用其他更高效的算法,如线性筛法等。

2.4 求素数的个数

题目描述

给定一个正整数 n n n,求小于或等于 n n n 的素数个数。

输入格式

一个正整数 n n n。 ( 1 ≤ n ≤ 1 0 6 ) (1 \leq n \leq 10^6) (1≤n≤106)

输出格式

输出小于或等于 n n n 的素数个数。

示例

输入:

10

输出:

4

输入:

100

输出:

25

解答

为了求小于或等于 n n n 的素数个数,我们可以使用埃拉托斯特尼筛法生成素数表,然后返回素数表的大小作为素数的个数。以下是使用C++实现的代码:

#include <iostream>
#include <vector>
using namespace std;

int countPrimes(int n) {
    const int N = n + 1;
    bool isPrime[N];
    vector<int> primes;
    
    fill(isPrime, isPrime + N, true);
    isPrime[0] = isPrime[1] = false;
    
    for (int i = 2; i < N; i++) {
        if (isPrime[i]) {
            primes.push_back(i);
            for (int j = i * i; j < N; j += i) {
                isPrime[j] = false;
            }
        }
    }
    
    return primes.size();
}

int main() {
    int n;
    cin >> n;
    cout << countPrimes(n) << endl;
    return 0;
}

代码解释:

1. 定义 countPrimes 函数,接受一个参数 n n n,表示要统计小于或等于 n n n 的素数个数。
2. 在函数内部定义布尔数组 isPrime,长度为 n + 1 n+1 n+1,初始时假设所有数都是素数,即将数组元素都设为 true。
3. 在函数内部定义整数数组 primes,用于存储生成的素数。
4. 使用埃拉托斯特尼筛法生成素数表。
   • 从 2 2 2 开始,遍历到 n n n,对于每个素数 i i i,将其倍数标记为合数。
   • 将每个素数加入到 primes 数组中。
5. 返回 primes 数组的大小,即为小于或等于 n n n 的素数个数。
6. 在主函数中,读入正整数 n n n,调用 countPrimes 函数统计小于或等于 n n n 的素数个数并输出结果。

这个方法直接在 countPrimes 函数内部使用埃拉托斯特尼筛法生成素数表,然后返回素数表的大小作为素数的个数。

需要注意的是,我们将数组 isPrime 的长度定义为 n + 1 n+1 n+1,以便能够标记从 0 0 0 到 n n n 的所有数。同时,在生成素数表时,我们只需要遍历到 n n n 即可,因为题目要求统计的是小于或等于 n n n 的素数个数。

时间复杂度: O ( n log ⁡ log ⁡ n ) O(n \log \log n) O(nloglogn)。
空间复杂度: O ( n ) O(n) O(n)。

这种方法简洁明了,通过生成素数表并返回素数表的大小,可以直接得到小于或等于 n n n 的素数个数。## 3. 素数的应用

3.1 素数的分解

3.1.1 试除法分解质因数

题目描述

给定一个正整数 n n n,将其分解为质因数的乘积形式。

输入格式

一个正整数 n n n。 ( 2 ≤ n ≤ 1 0 12 ) (2 \leq n \leq 10^{12}) (2≤n≤1012)

输出格式

以 n = p 1 e 1 × p 2 e 2 × ⋯ × p k e k n=p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_k^{e_k} n=p1e1​​×p2e2​​×⋯×pkek​​ 的形式输出 n n n 的质因数分解结果,其中 p i p_i pi​ 为质因数, e i e_i ei​ 为对应的指数,且 p 1 < p 2 < ⋯ < p k p_1<p_2<\cdots<p_k p1​<p2​<⋯<pk​。

示例

输入:

12

输出:

12=2^2*3^1

输入:

360

输出:

360=2^3*3^2*5^1

解答

试除法是一种简单直观的质因数分解方法。我们将给定的数 n n n 不断地除以从 2 2 2 开始的质数,直到 n n n 无法被整除为止。以下是使用C++实现的代码:

#include <iostream>
#include <vector>
using namespace std;

void factorize(int n) {
    vector<pair<int, int>> factors;
    
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            int count = 0;
            while (n % i == 0) {
                n /= i;
                count++;
            }
            factors.emplace_back(i, count);
        }
    }
    
    if (n > 1) {
        factors.emplace_back(n, 1);
    }
    
    cout << factors[0].first << "^" << factors[0].second;
    for (int i = 1; i < factors.size(); i++) {
        cout << "*" << factors[i].first << "^" << factors[i].second;
    }
    cout << endl;
}

int main() {
    int n;
    cin >> n;
    cout << n << "=";
    factorize(n);
    return 0;
}

代码解释:

1. 定义 factorize 函数,接受一个参数 n n n,表示要分解质因数的数。
2. 定义一个 vector<pair<int, int>> 类型的数组 factors,用于存储质因数和对应的指数。
3. 从 2 2 2 开始,遍历到 n \sqrt{n} n ​,对于每个数 i i i,判断 n n n 是否能被 i i i 整除。
   • 如果能整除,则将 i i i 作为质因数,并统计 i i i 的指数,同时将 n n n 除以 i i i。
   • 重复这个过程,直到 n n n 无法被 i i i 整除为止。
4. 如果最后 n n n 大于 1 1 1,说明 n n n 本身就是一个质因数,将其加入到 factors 数组中。
5. 按照题目要求的格式输出质因数分解的结果。
6. 在主函数中,读入正整数 n n n,调用 factorize 函数进行质因数分解并输出结果。

时间复杂度: O ( n ) O(\sqrt{n}) O(n ​)。
空间复杂度: O ( log ⁡ n ) O(\log n) O(logn),用于存储质因数和指数。

试除法是一种简单易懂的质因数分解方法,适用于小范围内的数。但是对于大数,试除法的效率较低,需要使用更高效的算法,如Pollard Rho算法。

3.1.2 Pollard Rho算法分解质因数

题目描述

给定一个正整数 n n n,将其分解为质因数的乘积形式。

输入格式

一个正整数 n n n。 ( 2 ≤ n ≤ 1 0 18 ) (2 \leq n \leq 10^{18}) (2≤n≤1018)

输出格式

以 n = p 1 e 1 × p 2 e 2 × ⋯ × p k e k n=p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_k^{e_k} n=p1e1​​×p2e2​​×⋯×pkek​​ 的形式输出 n n n 的质因数分解结果,其中 p i p_i pi​ 为质因数, e i e_i ei​ 为对应的指数,且 p 1 < p 2 < ⋯ < p k p_1<p_2<\cdots<p_k p1​<p2​<⋯<pk​。

示例

输入:

12

输出:

12=2^2*3^1

输入:

360

输出:

360=2^3*3^2*5^1

解答

Pollard Rho算法是一种概率性算法,用于快速分解大整数的质因数。它的基本思想是通过构造一个序列,利用生日悖论找到序列中的两个相同的数,从而得到一个因子。以下是使用C++实现的代码:

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

typedef long long ll;

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

ll pollard_rho(ll n, ll c) {
    ll x = 2, y = 2, d = 1;
    while (d == 1) {
        x = (x * x + c) % n;
        y = (y * y + c) % n;
        y = (y * y + c) % n;
        d = gcd(abs(x - y), n);
    }
    return d;
}

void factorize(ll n, unordered_map<ll, int>& factors) {
    if (n == 1) return;
    if (n % 2 == 0) {
        factors[2]++;
        factorize(n / 2, factors);
        return;
    }
    ll d = pollard_rho(n, 1);
    if (d == n) {
        factors[n]++;
    } else {
        factorize(d, factors);
        factorize(n / d, factors);
    }
}

int main() {
    ll n;
    cin >> n;
    unordered_map<ll, int> factors;
    factorize(n, factors);
    
    cout << n << "=";
    bool first = true;
    for (auto& factor : factors) {
        if (!first) cout << "*";
        cout << factor.first << "^" << factor.second;
        first = false;
    }
    cout << endl;
    
    return 0;
}

代码解释:

1. 定义 gcd 函数,用于计算两个数的最大公约数。
2. 定义 pollard_rho 函数,实现Pollard Rho算法。
   • 初始化两个变量 x x x 和 y y y 为 2 2 2,变量 d d d 为 1 1 1。
   • 通过构造序列 x i = ( x i − 1 2 + c )   m o d   n x_i=(x_{i-1}^2+c) \bmod n xi​=(xi−12​+c)modn 和 y i = ( y i − 1 2 + c )   m o d   n y_i=(y_{i-1}^2+c) \bmod n yi​=(yi−12​+c)modn,利用Floyd判圈算法找到序列中的相同数。
   • 计算 d = g c d ( ∣ x − y ∣ , n ) d=gcd(|x-y|, n) d=gcd(∣x−y∣,n),如果 d ≠ 1 d \neq 1 d=1,则找到了一个因子,返回 d d d。
3. 定义 factorize 函数,用于递归地进行质因数分解。
   • 如果 n n n 为 1 1 1,则直接返回。
   • 如果 n n n 为偶数,则将 2 2 2 作为质因数,并递归分解 n / 2 n/2 n/2。
   • 否则,调用 pollard_rho 函数找到一个因子 d d d。
     • 如果 d d d 等于 n n n,说明 n n n 本身就是一个质因数,将其加入到 factors 中。
     • 否则,递归分解 d d d 和 n / d n/d n/d。
4. 在主函数中,读入正整数 n n n,调用 factorize 函数进行质因数分解,并将结果存储在 unordered_map<ll, int> 类型的 factors 中。
5. 按照题目要求的格式输出质因数分解的结果。

Pollard Rho算法的时间复杂度取决于输入数 n n n 的大小和质因数的分布情况。在平均情况下,时间复杂度为 O ( n 1 / 4 ) O(n^{1/4}) O(n1/4),但在最坏情况下可能达到 O ( n 1 / 2 ) O(n^{1/2}) O(n1/2)。

需要注意的是,Pollard Rho算法是一种概率性算法,在某些情况下可能会失败。为了提高成功率,可以多次运行算法,或者与其他算法结合使用。

Pollard Rho算法适用于分解大整数的质因数,特别是当输入数比较大时,它的效率优于试除法。但是对于小范围内的数,试除法可能更加简单直观。

3.2 素数的幂次

3.2.1 求一个数分解质因数后各个素数的幂次

题目描述

给定一个正整数 n n n,将其分解质因数,并求出各个素数的幂次。

输入格式

一个正整数 n n n。 ( 2 ≤ n ≤ 1 0 18 ) (2 \leq n \leq 10^{18}) (2≤n≤1018)

输出格式

对于每个质因数 p i p_i pi​,输出其幂次 e i e_i ei​,每个质因数占一行。按照质因数从小到大的顺序输出。

示例

输入:

360

输出:

3
2
1

解释: 360 = 2 3 × 3 2 × 5 1 360=2^3 \times 3^2 \times 5^1 360=23×32×51,因此输出3、2、1。

解答

我们可以使用试除法来分解质因数,并同时统计每个质因数的幂次。以下是使用C++实现的代码:

#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;

vector<int> factorize(ll n) {
    vector<int> factors(100, 0);  // 假设质因数的个数不超过100
    
    for (ll i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            factors[i]++;
            n /= i;
        }
    }
    
    if (n > 1) {
        factors[n]++;
    }
    
    return factors;
}

int main() {
    ll n;
    cin >> n;
    vector<int> factors = factorize(n);
    
    for (int i = 2; i < factors.size(); i++) {
        if (factors[i] > 0) {
            cout << factors[i] << endl;
        }
    }
    
    return 0;
}

代码解释:

1. 定义 factorize 函数,接受一个参数 n n n,表示要分解质因数的数。
2. 创建一个长度为100的 vector<int> 类型的数组 factors,用于存储每个质因数的幂次。假设质因数的个数不超过100。
3. 从 2 2 2 开始,遍历到 n \sqrt{n} n ​,对于每个数 i i i,判断 n n n 是否能被 i i i 整除。
   • 如果能整除,则将 i i i 作为质因数,并统计 i i i 的幂次,同时将 n n n 除以 i i i。
   • 重复这个过程,直到 n n n 无法被 i i i 整除为止。
4. 如果最后 n n n 大于 1 1 1,说明 n n n 本身就是一个质因数,将其幂次加入到 factors 数组中。
5. 返回存储质因数幂次的数组 factors。
6. 在主函数中,读入正整数 n n n,调用 factorize 函数进行质因数分解,并获取质因数的幂次数组。
7. 遍历幂次数组,对于幂次大于0的质因数,输出其幂次。

时间复杂度: O ( n ) O(\sqrt{n}) O(n ​)。
空间复杂度: O ( 1 ) O(1) O(1),假设质因数的个数不超过100,数组的大小是固定的。

这个方法基于试除法,通过不断除以质因数来统计其幂次。由于我们使用了一个固定大小的数组来存储幂次,因此空间复杂度是 O ( 1 ) O(1) O(1)。如果质因数的个数可能很大,可以考虑使用 unordered_map 等数据结构来存储幂次。

3.2.2 求一个数的欧拉函数值

题目描述

给定一个正整数 n n n,求其欧拉函数值 φ ( n ) \varphi(n) φ(n)。欧拉函数 φ ( n ) \varphi(n) φ(n) 表示小于等于 n n n 且与 n n n 互质的正整数的个数。

输入格式

一个正整数 n n n。 ( 1 ≤ n ≤ 1 0 18 ) (1 \leq n \leq 10^{18}) (1≤n≤1018)

输出格式

输出 φ ( n ) \varphi(n) φ(n) 的值。

示例

输入:

12

输出:

4

解释:小于等于12且与12互质的正整数有1、5、7、11,共4个。

解答

求欧拉函数值可以利用欧拉函数的性质:对于一个正整数 n n n,如果 n = p 1 e 1 × p 2 e 2 × ⋯ × p k e k n=p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_k^{e_k} n=p1e1​​×p2e2​​×⋯×pkek​​,其中 p i p_i pi​ 为质因数, e i e_i ei​ 为对应的幂次,则 φ ( n ) = n × ( 1 − 1 p 1 ) × ( 1 − 1 p 2 ) × ⋯ × ( 1 − 1 p k ) \varphi(n)=n \times (1-\frac{1}{p_1}) \times (1-\frac{1}{p_2}) \times \cdots \times (1-\frac{1}{p_k}) φ(n)=n×(1−p1​1​)×(1−p2​1​)×⋯×(1−pk​1​)。

以下是使用C++实现的代码:

#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;

ll euler_phi(ll n) {
    ll res = n;
    for (ll i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            res = res / i * (i - 1);
            while (n % i == 0) {
                n /= i;
            }
        }
    }
    if (n > 1) {
        res = res / n * (n - 1);
    }
    return res;
}

int main() {
    ll n;
    cin >> n;
    cout << euler_phi(n) << endl;
    return 0;
}

代码解释:

1. 定义 euler_phi 函数,接受一个参数 n n n,表示要求欧拉函数值的数。
2. 初始化变量 res 为 n n n,表示欧拉函数的初始值。
3. 从 2 2 2 开始,遍历到 n \sqrt{n} n ​,对于每个数 i i i,判断 n n n 是否能被 i i i 整除。
   • 如果能整除,则将 i i i 作为质因数,根据欧拉函数的性质,将 res 乘以 ( 1 − 1 i ) (1-\frac{1}{i}) (1−i1​),即 res = res / i * (i - 1)。
   • 同时,将 n n n 除以 i i i,直到 n n n 无法被 i i i 整除为止,这样可以去除 i i i 的所有幂次。
4. 如果最后 n n n 大于 1 1 1,说明 n n n 本身就是一个质因数,根据欧拉函数的性质,将 res 乘以 ( 1 − 1 n ) (1-\frac{1}{n}) (1−n1​),即 res = res / n * (n - 1)。
5. 返回欧拉函数的值 res。
6. 在主函数中,读入正整数 n n n,调用 euler_phi 函数计算 φ ( n ) \varphi(n) φ(n) 的值并输出。

时间复杂度: O ( n ) O(\sqrt{n}) O(n ​)。
空间复杂度: O ( 1 ) O(1) O(1)。

这个方法基于欧拉函数的性质,通过分解质因数并计算每个质因数对欧拉函数值的贡献,最终得到欧拉函数的值。时间复杂度与分解质因数的过程相同,为 O ( n ) O(\sqrt{n}) O(n ​)。

需要注意的是,欧拉函数有一个重要的性质:如果 m m m 和 n n n 互质,则 φ ( m n ) = φ ( m ) × φ ( n ) \varphi(mn)=\varphi(m) \times \varphi(n) φ(mn)=φ(m)×φ(n)。利用这个性质,可以进一步优化欧拉函数的计算过程。

求欧拉函数值在数论和密码学中有重要应用,例如RSA加密算法的密钥生成过程中需要用到欧拉函数。

3.3 素数与最大公因数

3.3.1 求两个数的最大公因数(GCD)

题目描述

给定两个正整数 a a a 和 b b b,求它们的最大公因数。

输入格式

两个正整数 a a a 和 b b b,用空格分隔。 ( 1 ≤ a , b ≤ 1 0 18 ) (1 \leq a, b \leq 10^{18}) (1≤a,b≤1018)

输出格式

输出 a a a 和 b b b 的最大公因数。

示例

输入:

12 18

输出:

6

解释:12和18的最大公因数是6。

解答

求两个数的最大公因数可以使用欧几里德算法,也称为辗转相除法。基本思想是:如果 b b b 是 a a a 的约数,那么 g c d ( a , b ) = b gcd(a,b)=b gcd(a,b)=b;否则, g c d ( a , b ) = g c d ( b , a   m o d   b ) gcd(a,b)=gcd(b,a \bmod b) gcd(a,b)=gcd(b,amodb),通过不断递归直到 b b b 为0,此时 a a a 就是最大公因数。

以下是使用C++实现的代码:

#include <iostream>
using namespace std;

typedef long long ll;

ll gcd(ll a, ll b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int main() {
    ll a, b;
    cin >> a >> b;
    cout << gcd(a, b) << endl;
    return 0;
}

代码解释:

1. 定义 gcd 函数,接受两个参数 a a a 和 b b b,表示要求最大公因数的两个数。
2. 如果 b b b 为0,则 a a a 就是最大公因数,直接返回 a a a。
3. 否则,递归调用 gcd 函数,将 b b b 作为第一个参数,将 a a a 除以 b b b 的余数作为第二个参数。
4. 在主函数中,读入两个正整数 a a a 和 b b b,调用 gcd 函数计算它们的最大公因数并输出。

时间复杂度: O ( log ⁡ min ⁡ ( a , b ) ) O(\log \min(a, b)) O(logmin(a,b))。
空间复杂度: O ( log ⁡ min ⁡ ( a , b ) ) O(\log \min(a, b)) O(logmin(a,b)),为递归调用栈的深度。

欧几里德算法的时间复杂度与两个数的大小有关,具体来说,时间复杂度为两个数的较小值的二进制表示的位数。在最坏情况下,时间复杂度为 O ( log ⁡ min ⁡ ( a , b ) ) O(\log \min(a, b)) O(logmin(a,b))。

除了递归实现,还可以使用迭代的方式实现欧几里德算法:

ll gcd(ll a, ll b) {
    while (b != 0) {
        ll temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

迭代实现的时间复杂度与递归实现相同,但是空间复杂度降低为 O ( 1 ) O(1) O(1)。

求最大公因数在数论中有重要应用,例如约分分数、求解不定方程等。此外,最大公因数还可以用于优化一些算法,例如求解线性同余方程组。

3.3.2 求两个数的最小公倍数(LCM)

题目描述

给定两个正整数 a a a 和 b b b,求它们的最小公倍数。

输入格式

两个正整数 a a a 和 b b b,用空格分隔。 ( 1 ≤ a , b ≤ 1 0 18 ) (1 \leq a, b \leq 10^{18}) (1≤a,b≤1018)

输出格式

输出 a a a 和 b b b 的最小公倍数。

示例

输入:

12 18

输出:

36

解释:12和18的最小公倍数是36。

解答

求两个数的最小公倍数可以利用最大公因数和最小公倍数的关系:对于两个正整数 a a a 和 b b b,有 l c m ( a , b ) = a × b g c d ( a , b ) lcm(a,b)=\frac{a \times b}{gcd(a,b)} lcm(a,b)=gcd(a,b)a×b​。因此,我们可以先求出最大公因数,然后利用上述公式求出最小公倍数。

以下是使用C++实现的代码:

#include <iostream>
using namespace std;

typedef long long ll;

ll gcd(ll a, ll b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}

int main() {
    ll a, b;
    cin >> a >> b;
    cout << lcm(a, b) << endl;
    return 0;
}

代码解释:

1. 定义 gcd 函数,用于计算两个数的最大公因数,实现方式与之前相同。
2. 定义 lcm 函数,接受两个参数 a a a 和 b b b,表示要求最小公倍数的两个数。
3. 在 lcm 函数中,先调用 gcd 函数求出 a a a 和 b b b 的最大公因数,然后利用公式 l c m ( a , b ) = a × b g c d ( a , b ) lcm(a,b)=\frac{a \times b}{gcd(a,b)} lcm(a,b)=gcd(a,b)a×b​ 计算最小公倍数。
4. 在主函数中,读入两个正整数 a a a 和 b b b,调用 lcm 函数计算它们的最小公倍数并输出。

时间复杂度: O ( log ⁡ min ⁡ ( a , b ) ) O(\log \min(a, b)) O(logmin(a,b)),与求最大公因数的时间复杂度相同。
空间复杂度: O ( log ⁡ min ⁡ ( a , b ) ) O(\log \min(a, b)) O(logmin(a,b)),为递归调用栈的深度。

需要注意的是,在计算最小公倍数时,先将 a a a 除以最大公因数,再乘以 b b b,这样可以避免中间结果溢出。如果先将 a a a 和 b b b 相乘,再除以最大公因数,可能会导致中间结果溢出。

求最小公倍数在解决一些数学问题时很有用,例如求解同余方程组、计算分数的加减运算等。此外,最小公倍数还可以用于确定多个周期性事件的最小重复周期。

3.4 素数与同余

3.4.1 模运算和同余的概念
3.4.2 费马小定理及其应用
3.4.3 欧拉定理及其应用

4. 素数的进阶问题

4.1 素数的测试

4.1.1 费马素性测试
4.1.2 卡梅克尔数(Carmichael Number)

4.2 孪生素数

4.2.1 判断一对数是否为孪生素数
4.2.2 求一定范围内的孪生素数对

4.3 梅森素数(Mersenne Prime)

4.3.1 判断一个数是否为梅森素数
4.3.2 求第n个梅森素数

4.4 素数的和与积

4.4.1 戈德巴赫猜想(Goldbach’s Conjecture)
4.4.2 欧拉四平方和定理(Euler’s Four-Square Theorem)

这份练习目录包含了素数的基础知识、判断与筛选、应用以及一些进阶问题,涵盖了素数的多个方面。通过练习这些问题,可以加深对素数的理解和掌握。在实际编写代码时,需要注意算法的效率和优化。