L5_01 初等数论

一、素数与合数

1.1 定义

• 素数：大于1的正整数，除了1和它本身外没有其他因数
• 合数：大于1的正整数，除了1和它本身外还有其他因数

1.2 判断素数

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

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

int main() {
    cout << isPrime(17) << endl;  // 输出1（true）
    return 0;
}

---

二、最大公约数与最小公倍数

2.1 欧几里得算法（GCD）

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

2.2 最小公倍数（LCM）

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

---

三、同余与模运算

3.1 同余概念

若 a % m == b % m，则 a ≡ b (mod m)

3.2 模运算性质

// (a + b) % m = ((a % m) + (b % m)) % m
// (a * b) % m = ((a % m) * (b % m)) % m

---

四、约数与倍数

4.1 求约数

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

vector<int> getDivisors(int n) {
    vector<int> divisors;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            divisors.push_back(i);
            if (i != n / i) {
                divisors.push_back(n / i);
            }
        }
    }
    return divisors;
}

---

五、质因数分解

5.1 试除法

#include <iostream>
using namespace std;

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

---

六、奇偶性

6.1 判断奇偶

bool isEven(int n) {
    return n % 2 == 0;
}

bool isOdd(int n) {
    return n % 2 == 1;
}

---

七、素数表的埃氏筛法

7.1 算法原理

从2开始，将每个素数的倍数标记为合数。

7.2 代码实现

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

void sieve(int n) {
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;
    
    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            cout << i << " ";
        }
    }
}

---

八、线性筛法

8.1 算法原理

每个合数只被它的最小质因数筛掉。

8.2 代码实现

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

void linearSieve(int n) {
    vector<int> primes;
    vector<bool> isPrime(n + 1, true);
    
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            primes.push_back(i);
        }
        for (int p : primes) {
            if (i * p > n) break;
            isPrime[i * p] = false;
            if (i % p == 0) break;
        }
    }
    
    for (int p : primes) {
        cout << p << " ";
    }
}

---

九、唯一分解定理

9.1 定理内容

任何大于1的自然数都可以唯一分解为素数的乘积。

9.2 示例

12 = 2^2 × 3^1
36 = 2^2 × 3^2

---

十、示例程序

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

int main() {
    int a = 12, b = 18;
    
    cout << "GCD(" << a << ", " << b << ") = " << gcd(a, b) << endl;
    cout << "LCM(" << a << ", " << b << ") = " << a * b / gcd(a, b) << endl;
    
    return 0;
}