1.质数
定义:若一个正整数除了1和他自身外无法被其他自然数整除,该数则称为质数(又名素数),否则称为合数(又名合成数). 注意:1不是质数也不是合数
质数的判定: 如果在2~√n 内的整数能找到整除n的整数,则该数为合数,否则为质数.
质数的筛选:根据素数的倍数不是素数的原理,每次遍历到素数,其倍数都被标记为合数.根据这个原理便可以得到一定量的素数
利用埃氏筛(O(nlognlogn))可获得
//埃氏筛
const int maxn = 1e6 + 10;
int prime[maxn], primesize;
int vis[maxn];
void Prime(int n)//判断1~n内的素数的个数primesize并记录在prime内
{
memset(prime, 0, sizeof(prime));
memset(vis, 0, sizeof(vis));
for (int i = 2; i <= n; i++)
{
if (!vis[i])
{
prime[++primesize] = i;
}
for (int j = i; j <= n / i; j++)
{
vis[j*i] = 1;
}
}
}
_____________________________________________________________________________
也可以利用线性筛/欧拉筛(O(n))获得
//欧拉筛
int prime[maxn], primesize;
int vis[maxn];
void Prime(int n)
{
memset(prime, 0, sizeof(prime));
memset(vis, 0, sizeof(vis));
for (int i = 2; i <= n; i++)
{
if (!vis[i])
{
prime[++primesize] = i;
}
for (int j = 1; i <= n / prime[j] && j <= primesize; j++)
{
vis[i*prime[j]] = 1;
if (i%prime[j] == 0)
{
break;
}
}
}
}
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2.质因数分解
定义:任何一个大于1的正整数都能唯一分解为有限个质数的乘积.可写成
N=p1^a1 * p2^a2 * p3^ a3 * .......pk^ak. 其中p都是素数,a是p的指数.
跟据质数的判定以及质数的筛选,我们可以用代码得到一个数所含有的质因子的情况
//求单个数的质因数情况
const int maxn = 1e6;
int p[maxn], c[maxn];//p记录质因子 c记录质因子的指数值
void divide(int n)
{
int m = 0;
for (int i = 2; i <= sqrt(n); i++)
{
if (n%i == 0)//i是质数
{
p[++m] = i, c[m] = 0;
while (n%i == 0)n /= i, c[m]++;//除掉所有的i
}
}
if (n > 1)//n是质数
{
p[++m] = n, c[m] = 1;
}
}
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
3.约数
定义:若整数n除以d的余数为0,既d能整除n,则称d是n的约数,n是d的倍数,记为d|n.
算术基本定理的推论:若正整数N被唯一分解为N=p1^a1 * p2^a2 * p3^a3 *.......pk^ak 其中pi都是质数 ai都是正整数 ,则
N的正约数的个数为:
(a1 +1)*(a2+1)*(a3+1)*........*(ak+1);
N的所有正约数的和为:
(1+p1+p1^2+.......+p1^a1)*.......*(1+pk+pk^2+.......+pk^ak)
求1~N每个数的正约束集合----倍数法(O(nlogn))
对于每个数d,1~N中以d为约束的数就是d的倍数d,2d,3d...
//倍数法
const int maxn = 5e5 + 10;
//
vector<int> factor[maxn];
void fact(int n)
{
for (int i = 1; i <= n; i++)//以i为约数的数有
{
for (int j = 1; j <= n / i; j++)
{
factor[i*j].push_back(i);//加入其中
}
}
}
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
4.最大公约数
能同时整除自然数a与自然数b的最大自然数c
//欧几里得算法
int gcd(int a, int b)//求最大公约数
{
return b == 0 ? a : gcd(b, a%b);
}