# 整除的基本知识

给定一个正整数 n，求 1 到 n 中能够被 3 或 5 整除的所有整数之和。

#include <iostream>

using namespace std;

int main() {

    int n;

    cin >> n;

    int sum = 0;

    for (int i = 1; i <= n; i++) {

        if (i % 3 == 0 || i % 5 == 0) {

            sum += i;

        }

    }

    cout << sum << endl;

    return 0;

}

# 质数与合数

质数，又称素数，是指除了 1 和本身外没有其他因数的正整数。例如，2、3、5、7、11 等都是质数。而合数则是指除了 1 和本身以外还有其他因数的正整数，例如 4、6、8、9、10 等都是合数。

每个正整数都可以唯一地分解为若干个质数的乘积，这个过程称为质因数分解。例如，12 = 2 × 2 × 3，其中 2 和 3 是 12 的素因数。

判断一个数是否为质数的方法有很多种，比较常见的方法是试除法。即对于一个正整数 n，从 2 到 sqrt (n) 的范围内枚举所有的数，判断它们是否能够整除 n，如果存在一个数 m 能够整除 n，则 n 不是质数；否则，n 是质数。

给定一个正整数 n，求小于等于 n 的所有质数的和。

#include <iostream>

using namespace std;

// 判断一个数是否为质数

bool is_prime(int n) {

    if (n < 2) return false;

    for (int i = 2; i * i <= n; i++) {

        if (n % i == 0) return false;

    }

    return true;

}

int main() {

    int n;

    cin >> n;

    int sum = 0;

    for (int i = 2; i <= n; i++) {

        if (is_prime(i)) {

            sum += i;

        }

    }

    cout << sum << endl;

    return 0;

}

# 最大公约数与最小公倍数

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

#include <iostream>

using namespace std;

// 计算最大公约数

int gcd(int a, int b) {

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

}

// 计算最小公倍数

int lcm(int a, int b) {

    return a * b / gcd(a, b);

}

int main() {

    int a, b;

    cin >> a >> b;

    int g = gcd(a, b);

    int l = lcm(a, b);

    cout << g << " " << l << endl;

    return 0;

}

# 算术基本定理

算术基本定理又称为质因数分解定理，它指出：每一个大于 1 的正整数都可以唯一地分解为质数的积。例如，12 可以分解为 $2^2 \times 3$，而 35 可以分解为 $5 \times 7$。

更正式地说，算术基本定理可以表述如下：

设正整数 $n$，则 $n$ 可以唯一地表示成如下形式：

$$n = p_1^{k_1} \times p_2^{k_2} \times \cdots \times p_m^{k_m}$$

其中 $p_1, p_2, \cdots, p_m$ 是 $m$ 个不同的质数，$k_1, k_2, \cdots, k_m$ 是 $m$ 个非负整数。

容易证明，任何一个大于 1 的正整数都可以用上述形式表示，并且这种表示方法是唯一的。

算术基本定理在数论中有着广泛的应用，例如，对于一个数 $n$，如果我们能够对它进行质因数分解，那么就可以方便地求出它的约数个数和约数之和等信息，或者判断它是否为完全平方数等问题。

质因数分解的算法很多，其中最简单的是试除法，即从小到大枚举所有小于等于 $n$ 的质数，如果某个质数 $p$ 能够整除 $n$，则不断除以 $p$ 直到无法整除为止，这样就得到了 $n$ 的质因数分解。

例如，对于数 $12$，我们可以从 $2$ 开始枚举所有的质数，发现 $2$ 是 $12$ 的一个质因数，于是我们将 $12$ 不断地除以 $2$，得到 $12 = 2^2 \times 3$。