1.素数
素数（Prime Number）是指大于1的自然数，只有两个正因数：1和它自身。换句话说，素数是不能被其他自然数整除的数。
1.1小素数的判定
判定一个数是否为素数 ，当N ≤ 时， 用试除法 ， 当n >
时 ， 用Miller_Rabin算法
根据素数的定义，可以直接得到试除法 ， 用[2,n - 1] 内的所有数着除n，如果不能整除 ， 就是素数，很容易发现 可以把[2 , n - 1] 缩小到 , [2,]
试除法的时间复杂度为O（n），N ≤ 时够用 ， 以下为试除法的实现代码：
#define int long long
bool is_prime(int n)
{
if(n <= 1) return false;
for(int i = 2;i * i <= n;i ++)
{
if(n % i == 0) return false;
}
return true;
}
//i * i <= n 也可以写成 i < n / i1.2大素数的判定
本章介绍大素数的判定的两种方法
如果N 非常大 试除法就不够用了
一般采用Miller_Rabin素行测试算法 ，由于这个算法过于复杂 就不在这里介绍这个算法了
2.分解质因数
什么是质因数？
质因数（Prime Factor）是指一个整数的质数因子。换句话说，质因数是能够整除该整数的质数。每个大于1的自然数都可以被唯一分解为质因数的乘积，这称为质因数分解。
void divide(int x)
{
for(int i = 2;i <= x / i;i ++)
{
if(x % i == 0) //以x为底数
{
int s = 0; //s为指数
while(x % i == 0) x /= i , s++;
cout << i << ' ' << s << endl;
}
}
if(x > 1) cout << x << ' ' << 1 << endl;
cout << endl;
}3.素数筛
主要用于筛选1 ~ n 中的素数的个数
有两种方法 ：
3.1.埃氏筛发（传统的 时间复杂度O(nlognlongn）)
代码实现：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int prime[N]; //存储素数 visit[i]为false的项
bool vis[N]; //true表示被筛掉 不是素数
int E_sieve(int n) //埃氏筛法
{
int k = 0; //统计个数
for(int i = 0;i <= n;i ++) vis[i] = false;
for(int i = 2;i <= n;i ++)
{
if(!vis[i])
{
prime[k++] = i;
for(int j = 2 * i;j <= n;j += i)
// 可以优化成 j = i * i
{
vis[j] = true;
}
}
}
return k;
}
int main()
{
int n;
cin >> n;
cout << E_sieve(n) << endl;
return 0;
}3.2.欧拉筛（时间复杂度O（n））
欧拉筛的原理：
欧拉筛是一种线性筛法 ， 能在O（n） 的线性时间求得1~N内所有的素数 欧拉筛是对埃氏筛的一种改进
原理：一个合数肯定有一个最小的质因数；让没个合数只被他的最小质因数筛选一次 ，达到不重复筛的目的；
具体操作：
1：逐一检查2~n的所有数 第一个检查的是 2 ， 他是第一个素数
2：当检查到第i个数时，利用已经求得的素数去筛掉对应的合数x ， 而且是用x的最小质因数去筛
代码实现：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10; // 定义常量N为1000010，表示素数的上限
int prime[N]; // 存储素数的数组，visit[i]为false的项
bool vis[N]; // vis[i]表示i是否被筛掉，true表示i不是素数
// 欧拉筛法，返回小于等于n的素数个数
int euler_sieve(int n) {
int cnt = 0; // 计数器，用于记录素数的个数
memset(vis, 0, sizeof(vis)); // 初始化vis数组，所有项设为false
memset(prime, 0, sizeof(prime)); // 初始化prime数组
// 从2开始，遍历到n
for (int i = 2; i <= n; i++) {
// 如果vis[i]为false，说明i是一个素数
if (!vis[i]) {
prime[cnt++] = i; // 将素数i存入prime数组，并增加计数
}
// 遍历所有已找到的素数
for (int j = 0; j < cnt; j++) {
// 只筛选小于等于n的数
if (i * prime[j] > n) break; // 如果i * prime[j]大于n，停止循环
vis[i * prime[j]] = 1; // 用i的最小质因数筛去i的倍数
// 如果i能被当前的素数prime[j]整除
if (i % prime[j] == 0) break; // 结束内层循环，确保筛选的质因数是最小的
}
}
return cnt; // 返回素数的个数
}
int main() {
int n;
cin >> n; // 输入n
cout << euler_sieve(n) << endl; // 输出小于等于n的素数个数
return 0;
}
2.约数
约数的定义：约数是指能够整除一个整数的整数。换句话说，如果一个整数 a 能被另一个整数 b 整除，且没有余数，那么 b 就称为 a 的一个约数。
如果 n mod b =0，则 b 是 n 的约数。
2.1试除法求约数
以下是带有详细注释的代码：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void solve()
{
int n;
cin >> n;
vector<int> res;
// 遍历 1 到 n 的平方根，查找 n 的约数
for(int i = 1; i <= n / i; i++)
{
if(n % i == 0)
{
res.push_back(i);
if(n / i != i) // 避免重复添加
{
res.push_back(n / i);
}
}
}
sort(res.begin(), res.end()); // 对结果数组进行排序
for(auto e : res)
{
cout << e << " "; // 输出约数
}
cout << endl;
}
int main()
{
int t;
cin >> t; // 读取测试用例的数量
while(t--)
{
solve();
}
return 0;
}
2.2 约数的个数
#include <iostream>
#include <unordered_map>
using namespace std;
typedef long long LL;
const int N = 110, 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; // 除以素数 i
primes[i]++; // 记录素数 i 的出现次数
}
}
if (x > 1) primes[x]++; // 如果 x 是素数，则记录
}
LL res = 1; // 初始化结果
// 计算约数个数
for (auto p : primes)
res = res * (p.second + 1) % mod; // 根据公式计算约数个数并取模
cout << res << endl; // 输出结果
return 0; // 程序正常结束
}
2.3约数之和
代码实现 + 详细注释
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;
typedef long long LL; // 定义长整型别名
const int N = 110, mod = 1e9 + 7; // 常量 N 和模数 mod
int main()
{
int n;
cin >> n; // 读取要处理的数字的个数
unordered_map<int, int> primes; // 存储素因数及其对应的次数
while (n -- ) // 对每个数字进行处理
{
int x;
cin >> x; // 读取数字 x
// 进行素因数分解
for (int i = 2; i <= x / i; i ++ ) // 遍历从 2 到 sqrt(x)
while (x % i == 0) // 如果 i 是 x 的因数
{
x /= i; // 将 x 除以 i
primes[i] ++ ; // 记录素因数 i 的次数
}
// 如果 x 大于 1，说明 x 本身是一个素数
if (x > 1) primes[x] ++ ; // 将素数 x 也加入到 primes 中
}
LL res = 1; // 初始化结果为 1
for (auto p : primes) // 遍历所有的素因数及其次数
{
LL a = p.first, b = p.second; // a 为素因数，b 为该素因数的指数
LL t = 1; // 初始化每个因数的约数和为 1
while (b -- ) // 对于每个素因数的指数
t = (t * a + 1) % mod; // 计算 (1 + a + a^2 + ... + a^b) 的值
res = res * t % mod; // 将当前素因数的约数和与结果相乘，并对 mod 取模
}
cout << res << endl; // 输出最终结果
return 0;
}
2.4.最大公约数（GCD）
整除的定义：：
1.GCD的定义：
#include<iostream>
using namespace std;
int gcd(int a , int b)
{
return b ? gcd(b , a % b) : a;
}
int main()
{
int t;
cin >> t;
while(t--)
{
int a , b;
cin >> a >> b;
cout << gcd(a , b) << endl;
}
return 0;
}
