这期博客是一个数论入门介绍，大佬们请路过
前言：这期的数论包括哪些内容：
基本概念
- 整数的基本性质: 奇偶性、整除性、质数和合数等。
- 素数（质数）: 素数的定义、素数筛法（如埃拉托斯特尼筛法）和素数分解。
- 最大公约数 (GCD) 和 最小公倍数 (LCM): 欧几里得算法、扩展欧几里得算法（用于求解线性同余方程）。
1.素数(质数)
说到数论，小学奥数里也有。我最先想到的就是质数了。素数就是一个只能被1和它自己整除的数。判断的方法也很简单，可以扫一遍就结束了，但是没必要。由于一个数的因数肯定分布在
的左边和右边。因此，只用扫描到
就够了。
bool isprime(int n){if(n<2)//0和1都不是质数 return false;for(int i=2;i<=n/i;i++){//这里i<=n/i是一个防止i*i爆int以及sqrt(n)精度不好的小技巧 if(n%i==0)return false;}return true;
}现在，我们知道如何判断一个数是不是质数的方法了。现在，我们向分解G(质因)数。我们Θ(n−−√)Θ(n)的扫描，只要i是n的因数，就把i塞进一个map里，然后除掉n里面所有的i。这样就保证了每个i都是素数，顺便记录次数。最后，有可能n不为0，所以要特判。
map<int,int> fac;//分别是:质因子,次数
for(int i=2;i<=n/i;i++){if(n%i==0){while(n%i==0){n/=i;fac[i]++;}}
}
if(n!=1)//特判fac[n]=1;
1.1筛法求素数
基本思路是:素数的倍数不是素数
1不是素数首先把它筛掉，剩下的数中最小的数一定是素数，然后去掉它的倍数。
// 从 2 到 n 遍历所有整数
for(int i=2;i<=n;i++){// 如果当前数 i 没有被标记为合数，则它是一个素数if(!vis[i]){// 将素数 i 存储在 prime 数组中，并更新素数计数器 cntprime[++cnt]=i;// 将所有 i 的倍数标记为合数for(int j=1;j*i<=n;j++) vis[i*j]=true;}
}
但是我们注意到，这样筛会筛重很多次。
我们拿75 举例 :在筛到素数3时我们把它筛除 在筛到素数5时我们又会筛除一次 这样会浪费大量的时间，如何优化呢？
1.2线性筛
基本思路是:在筛法的基础上 我们让每一个合数只能被他自己最小的素数筛到
// 从 2 到 n 遍历所有整数
for(int i=2;i<=n;i++){// 如果当前数 i 没有被标记为合数，则它是一个素数if(!vis[i]) prime[++cnt] = i;// 对于每一个素数 prime[j]（直到当前已找到的素数个数 cnt），// 将 i 乘以 prime[j] 的结果标记为合数for(int j=1; j<=cnt && i*prime[j] <= n; j++){vis[i*prime[j]] = true;// 如果 i 能被 prime[j] 整除，则停止进一步的倍数标记if(i % prime[j] == 0) break;}
}
例题：求1~n中质数的个数
#include<iostream>
using namespace std;const int N = 1000010; // 最大范围
int st[N], cnt, primes[N]; // st 用于标记合数，primes 存储素数，cnt 记录素数数量// 获取小于等于 n 的所有素数
void get_primes(int n) {for(int i = 2; i <= n; i++) {// 如果 i 不是合数，则 i 是素数if(!st[i]) primes[cnt++] = i;// 将 i 乘以当前所有素数 primes[j] 的结果标记为合数for(int j = 0; primes[j] <= n / i; j++) {st[primes[j] * i] = true;// 如果 i 能被 primes[j] 整除，则停止标记倍数if(i % primes[j] == 0) break;}}
}int main() {int n;cin >> n; // 输入 nget_primes(n); // 获取所有小于等于 n 的素数cout << cnt << endl; // 输出素数的数量return 0;
}