质数（素数）、约数

一、质数：
若一个正整数无法被除了1和它自身之外的任何自然数整除，则称该数为质数（或素数），
否则称该正整数为合数。
1不是素数，2是最小的素数。
在整个自然数集合中，质数的数量不多，分布比较稀疏，
对于一个最够大的整数 N，不超过 N 的质数大约有 $\frac{N}{lnN}$lnNN​个，即每lnN个数大约有1个质数。

二、素数表的获取——Eratosthenes筛法：
小于x*x的x的倍数在扫描更小的数时就已经被标记过了。
对于某一个合数，其倍数一定在某个比其小的质数（其质因数）筛掉了。
时间复杂度为O（N loglogN）接近线性。

#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;
}

四、质因数分解（唯一分解）：
对一个正整数n来说，如果它存在【2，n】范围内的质因子，要么这些质因子全部都小于等于sqrt（n），要么只存在一个大于sqrt（n）的质因子，而其余质因子全部都小于sqrt（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!中质因子 p 的个数就等于 $1-N$1−N中每个数包含质因子 $p$p的个数之和。在 $1-N$1−N中， $p$p的倍数，即至少包含一个质因子 $p$p的显然有 $\left[N/p\right]$[N/p]个。而 $p^2$p2 的倍数，即制定好包含2个质因子 $p$p的有 $\left[N/p²\right]$[N/p²]个。不过其中的一个质因子已经在 $\left[N/p\right]$[N/p]里统计过，所以只需要再统计第2个质因子，即累加上 $\left[N/p²\right]$[N/p²]。
即 $\left[N/p\right]+\left[N/p^2\right]+\left[N/p^3\right]\dots \dots O（logN）$[N/p]+[N/p2]+[N/p3]……O（logN）

int fi(int n,int p)
{
    int ans=0;
    while(n)
    {
        ans+=n/p;
        n=n/p;
    }
    return ans;
}

六、约数：
对于某一正整数N，已唯一分解。
$pi，ei。$pi，ei。
$N的正约数的个数为（e1+1）\ast （e2+1）\ast \dots \dots （ei+1）=\Pi （ei+1）$N的正约数的个数为（e1+1）∗（e2+1）∗……（ei+1）=Π（ei+1）
$N的正约数的和为（1+p1+p{1}^2+\dots \dots ）\dots \dots （1+pi+p{i}^2\dots \dots ）=\frac{（1-p{1}^{(e1+1)})}{(1-p1)}\times \frac{（1-p{2}^{(e2+1)})}{(1-p2)}\times \dots \dots \times \frac{（1-p{i}^{(ei+1)})}{(1-pi)}（手写快速幂）$N的正约数的和为（1+p1+p12+……）……（1+pi+pi2……）=(1−p1)（1−p1(e1+1))​×(1−p2)（1−p2(e2+1))​×……×(1−pi)（1−pi(ei+1))​（手写快速幂）

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的正约数集合——试除法：
除了完全平方数sqrt（n）会单独出现，其余约数总是成对出现的。
d=1–sqrt（n），时间复杂度为O（sqrt（n））
根据实际测算 10⁹ 以内的自然数中，约数个数最多的自然数仅有1536个约数。

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），那么称x为反质数。例如整数1，2，4，6等都是反质数。现给定一个数N（1—2*10⁹ )，求不超过N的最大的反质数。

1。1–N中最大的反质数，就是1–N中约数个数最多的数中最小的一个。
2。1–N中任何数的不同质因子都不会超过10个，且所有质因子的指数总和不超过30。
3。任何x属于1–N，x为反质数的必要条件是：x分解质因数后可写作：
2^c1*3^c2*5^c3*7^c4*11^c5*13^c6*17^c7*19^c8*23^c9*29^c10，并且c1>=c2>=……c10>=0。通俗的讲，x的质因子是连续的若干个最小的质数，并且指数单调递减。

DFS深搜，尝试一次确定前10个质数的指数，并满足指数单调递减、总乘积不超过N，同时记录约数的个数。

十、最大公约数：
1。任意自然数a，b。 $gcd（a，b）\times lcm（a，b）=a\times b$gcd（a，b）×lcm（a，b）=a×b。

2。更相减损：
$a\ge b：gcd(a,b)=gcd(b,a-b)=gcd(a,a-b)$a≥b：gcd(a,b)=gcd(b,a−b)=gcd(a,a−b)
$gcd(2a,2b)=2gcd(a,b)$gcd(2a,2b)=2gcd(a,b)

3。欧几里得算法：
$b\ne 0：gcd(a,b)=gcd(b,amodb)$b​=0：gcd(a,b)=gcd(b,a mod b)
时间复杂度为O（log（a+b））。

int gcd(int a,int b)
{
    if(b==0) return a;
    return gcd(b,a%b);
}