质数（素数）、约数
一、质数：
若一个正整数无法被除了1和它自身之外的任何自然数整除，则称该数为质数（或素数），
否则称该正整数为合数。
1不是素数，2是最小的素数。
在整个自然数集合中，质数的数量不多，分布比较稀疏，
对于一个最够大的整数 N，不超过 N 的质数大约有\frac{N}{lnN}个，即每lnN个数大约有1个质数。
二、素數表的獲得——埃拉托斯特尼篩法：
這些x值对应的最小倍數已经在扫描更小数字时就被标记了。
每一個合成數都会在其較小的一個質因數值上被筛掉。
計算複雜度約為O(N \log \log N), 接近線性。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=1000005;
bool v[maxn];
void init(int n)
{
memset(v,0,sizeof(v));
v[1]=true;
for(int i=2;i<=n;i++)
{
if(v[i]) continue;
for(int j=i;j<=n/i;j++)
v[i*j]=true;
}
return ;
}
int main(void)
{
int n;
scanf("%d",&n);
init(n);
for(int i=1;i<=n;i++)
{
if(!v[i])
printf("%d ",i);
}
return 0;
}三、素数表的获取——欧拉线性筛：
1.
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=1000005;
int v[maxn],prime[maxn];
int cnt=0;
void init(int n)
{
memset(v,0,sizeof(v));
v[1]=1;
for(int i=2;i<=n;i++)
{
if(v[i]==0)
{
v[i]=i;
prime[cnt++]=i;
}
for(int j=0;j<cnt;j++)
{
if(prime[j]>v[i]||prime[j]>n/i) break;
v[i*prime[j]]=prime[j];
}
}
return ;
}
int main(void)
{
int n;
scanf("%d",&n);
init(n);
for(int i=0;i<cnt;i++)
printf("%d ",prime[i]);
return 0;
} #include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=1000005;
int prime[maxn];
bool ha[maxn];
int cnt=0;
void Prime(int n)
{
memset(ha,0,sizeof(ha));
ha[1]=true;
for(int i=2;i<=n;i++)
{
if(!ha[i])
prime[cnt++]=i;
for(int j=0;j<cnt&&prime[j]<=n/i;j++)
{
ha[i*prime[j]]=true;
if(i%prime[j]==0) break;
}
}
return ;
}
int main(void)
{
int n;
scanf("%d",&n);
Prime(n);
for(int i=0;i<cnt;i++)
printf("%d ",prime[i]);
return 0;
}2, n
任何一个合数n必定包含一个不超过sqrt（n）的质因子。
两种分解方法：
1.先素数筛把把素数筛出来，然后对素数进行遍历找质因数。
2.直接从2–sqrt（n）找质因数（时间复杂度O（sqrt（n）））。
对于（2）因为一个合数的因子一定在扫描到这个合数之前就从N中被除掉了，所以在上述过程中能整除N的一定是质数。最终得到了质因数分解的结果。
特别的，若 N 没有被任何2–sqrt（N）的数整除，则N是质数，无需分解。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=1000005;
int prime[maxn];
bool ha[maxn];
int cnt=0;
void Prime(int n)
{
memset(ha,0,sizeof(ha));
ha[1]=true;
for(int i=2;i<=n;i++)
{
if(!ha[i])
prime[cnt++]=i;
for(int j=0;j<cnt&&prime[j]<=n/i;j++)
{
ha[i*prime[j]]=true;
if(i%prime[j]==0) break;
}
}
return ;
}
int p[30],e[30];
void only(int n)
{
memset(p,0,sizeof(p));
memset(e,0,sizeof(e));
int _cnt=0;
for(int i=0;i<cnt&&prime[i]*prime[i]<=n;i++)
{
if(n%prime[i]) continue;
p[++_cnt]=prime[i];
while(n%prime[i]==0)
{
e[_cnt]++;
n/=prime[i];
}
if(n==1) break;
}
if(n>1) p[++_cnt]=n,e[_cnt]=1;
for(int i=1;i<=_cnt;i++)
printf("%d:%d\n",p[i],e[i]);
return ;
}
int main(void)
{
int n;
scanf("%d",&n);
Prime(n);
only(n);
for(int i=0;i<cnt;i++)
printf("%d ",prime[i]);
return 0;
}五、阶乘分解：
在n!(n≥1)中质因子p(p≥2)的总个数等于从n/p!~n=1到n=n的所有整数值中包含至少一个质因数p的数量之和。对于区间中的每个整数值$k~(k=1到n)$来说，在其分解质因数的过程中至少会包含一个$p~。同样地，在寻找包含两个$p$s的部分时，则需要考虑$k能被p^2~整除的情况。需要注意的是，在计算包含一个p$s的部分时已经统计过这些情况……因此，在后续步骤中只需关注那些仅含有两个或更多个的情况。将上述所有部分相加即可得到最终结果……这个过程的时间复杂度为O(log N)
int fi(int n,int p)
{
int ans=0;
while(n)
{
ans+=n/p;
n=n/p;
}
return ans;
}六、约数：
int mypow(int a,int b)
{
int ans=1;
while(b)
{
if(b&1) ans*=a;
a*=a;
b>>=1;
}
return ans;
}
int ans=1;
for(int i=1;i<=_cnt;i++)
{
ans*=(e[i]+1);
}
int sum=1;
for(int i=1;i<=_cnt;i++)
{
sum*=(mypow(p[i],e[i]+1)-1)/(p[i]-1);
}七、求 N 的正约數集合——試除法：
除完全平方數√N外的所有正整數值均會成雙成對地出現。
其中 d 的取值範圍是从 1 到 √N 的整數值，并具備計算複雜度 O(√N)。
通過實際測算，在小於等於 2^99 的自然數值範圍內寻找拥有最多正因数值的那个数字時所消耗的时间。
int fa[1600],cnt=0;
for(int i=1;i*i<=n;i++)
{
if(n%i==0)
{
fa[++cnt]=i;
if(i!=n/i) fa[++cnt]=n/i;
}
}
for(int i=1;i<=m;i++)
cout<<fa[i]<<endl;推论：一个整数N的约数个数上届为2sqrt（n）。
八、求1–N每个数的正约数集合——倍数法：
时间复杂度为O（nlogn）。
vector<int>fa[500010];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n/i;j++)
fa[i*j].push_back(i);
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<fa[i].size();j++)
printf("%d ",fa[i][j]);
putchar('\n');
}推论：1–N每个数的约数个数的总和大约为NlogN。
九、反素數：
對於任何一個正整數x來說،我們用g(x)來表示其約數個數。例如,g(1)=1,g(6)=4等例子可見一二。
當且僅当下列表述成立時, 我們稱x為反素數: 對於所有滿足0 < i < x的情況, 都有g(x) > g(i)成立。**例如**, 整數1, 2, 4, 6等皆為典型反素數。**現給定一個數值N, 與其範圍限定在區間\left[ {1,\;2 \times {10^9}} \right]之間, 請問不大於此N的最大反素數為何。\
最大反子在区间内是最高的；它对应的是该区间内因数量最多的一个最小值。
对于区间内的任意一个元素来说，在其素因子分解时最多包含十个不同的素因子，并且这些素因子的指数之和不会超过三十。
当考虑区间内的某个元素作为反子时，则必须满足以下条件：它能表示为前十个连续素因子的幂次方乘积形式即2c₁×3c₂×5c₃×7c₄×...×29^c₁₀，并且这些幂次必须满足非递增排列的关系即 c₁≥ c₂≥ ... ≥ c₁₀≥ 0。换言之，在这种情况下该元素的所有素因子都是连续的一些最小素数组成的，并且它们各自的幂次呈非递增趋势排列。
深度优先搜索（DFS）算法，在单次运行中确定前10个质因数及其对应的指数，并要求各质因数的指数依次递减以确保乘积不大于给定值N，并统计相应的因数数目。
十、最大公约数：
1。任意自然数a，b。gcd（a，b）×lcm（a，b）=a×b。
2。更相减损：
a≥b：gcd(a,b)=gcd(b,a-b)=gcd(a,a-b)
gcd(2a,2b)=2gcd(a,b)
3。欧几里得算法：
b≠0：gcd(a,b)=gcd(b,a\space mod\space b)
时间复杂度为O（log（a+b））。
int gcd(int a,int b)
{
if(b==0) return a;
return gcd(b,a%b);
}