ACM算法复习笔记——素数与合数

素数

素数是指大于1的自然数中，除了1和它本身外没有其他因数的数。

素数的判定

暴力求解法

单个数的判定：遍历从2到n的所有整数，判断n是否能被这些整数整除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# include <iostream>

using namespace std;

bool is_prime(int n) {
    // judge if n is a prime number
    if(n <= 1) return false; // 1 and less are not prime numbers
    for(int i=2; i*i <= n; i++) {
        if(n%i == 0) {
            return false; // n is divisible by i, so it's not a prime number
        }
    }
    return true; // n is a prime number
}

素数表的构建：构建素数表，同时确认范围内的所有数是否为素数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <vector>

using namespace std;

vector<bool> is_prime(int n) {
    vector<bool> prime(n+1, true); // Create a vector to store prime status
    prime[0] = prime[1] = false; // 0 and 1 are not prime numbers
    for(int i=2; i*i <= n; i++) {
        if(prime[i]) { // If i is prime
            for(int j=i*i; j<=n; j+=i) {
                prime[j] = false; // Mark multiples of i as not prime
            }
        }
    }
}

线性筛

线性筛是一种高效的素数筛选算法，时间复杂度为 O(nloglogn)O(nloglogn)，适用于大范围内的素数筛选。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <vector>

using namespace std;

vector<bool> linear_sieve(int n) {
    vector<bool> prime(n+1, true);
    vector<int> primes; // Store the prime numbers
    prime[0] = prime[1] = false; // 0 and 1 are not prime numbers
    for(int i=2; i<n; i++) {
        if(prime[i]) {
            primes.push_back(i); // i is a prime number
        }
        for(int j=0; j<primes.size() && primes[j] < n/i; j++) {
            prime[primes[j]*i] = false; // Mark multiples of primes as not prime
            if(i % primes[j] == 0) break;
        }
    }
    return prime; 
}

欧拉函数

欧拉函数 ϕ(n)\phi(n) 是指小于等于 nn 的正整数中，与 nn 互质的数的个数。

欧拉函数的计算

欧拉函数可以通过以下公式计算：

ϕ(n)=n(1−1p1)(1−1p2)⋯(1−1pk)\phi(n) = n \left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_k}\right)

其中 p1,p2,…,pkp_1, p_2, \ldots, p_k 是 nn 的所有不同的质因数。

暴力法

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

算法思想：逐个计算每个质因数，代入上述公式中计算，找到一个质因数之后需要将 nn 除以该质因数，直到 nn 不能被该质因数整除为止。最后如果 nn 仍然大于1，则 nn 本身也是一个质因数，需要再进行一次计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <vector>

using namespace std;

int  get_euler(int n) {
    int res = n;
    for(int i=2; i*i <= n; i++) {
        if(n % i == 0) {
            res = res / i * (i-1);
            while(n%i == 0) {
                n /= i; // Remove all factors of i from n
            }
        }
    }
    // If n is still greater than 1, it is a prime factor
    return n > 1 ? res / n * (n-1) : res; 
}

线性筛法

时间复杂度：O(n)O(n)

算法思想：使用线性筛法计算素数，然后利用素数计算欧拉函数。对于每个素数 pp，如果 pp 是 nn 的质因数，则 ϕ(n)=n×(1−1p)\phi(n) = n \times (1 - \frac{1}{p})，否则 ϕ(n)=ϕ(n)\phi(n) = \phi(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <vector>

using namespace std;

vector<int> get_euler(int n) {
    vector<int> phi(n+1);
    // Initialize phi array
    for(int i=1; i<=n; i++) {
        phi[i] = i; 
    }
    // 线性筛
    for(int i=2; i<=n; i++) {
        if(phi[i] == i) { // i is a prime number
            for(int j=i; j<=n; j+=i) {
                phi[j] = phi[j] / i * (i-1); // Update phi value
            }
        }
    }
    return phi;
}