质数

试除法判断是否为质数

726. 质数

bool is_prime(int x)
{
    for(int i=2;i<=x/i;i++)
    {
        if(x%i==0)
            return false;
    }
    return true;
}

筛质数

埃氏筛法

int prime[N],st[N];
void (int n)
{
    int cnt=0; 
    for(int i=2;i<=n;i++)
    {
        if(st[N]) continue;
        prime[cnt++]=i;
        for(int j=i+i;j<=n;j+=i)    st[j]=true;
    }
}

线性筛法

int cnt=0;
for(int i=2;i<=n;i++)
{
    if(!st[i])  prime[cnt++]=i;
    for(int j=0;i*prime[j]<=n;j++) //通过最小质因子来筛走数,注意判断条件
    {
        st[prime[j]*i]=true;
        if(i%prime[j]==0)   break;
    }
}

分解质因数

试除法求质因数
449. 质因数分解(用哪种看题目需要和x的范围)

//一定要记得对那个可能存在的大于根号x的质因数进行特判处理O(n^1/2)
int main()
{
    cin>>x;
    for(int i=2;i<=x/i;i++)
    {
        if(x%i==0)
        {
            int cnt=0;
            while(x%i==0)
            {
                cnt++;
                x/=i;
            }
            cout<<x<<" "<<cnt<<endl;
        }
    }
    if(x>1) cout<<x<<" 1";
}

约数

约数是建立在质因数分解的基础上进行的
约数个数最多1500个(粗略)

试除法求所有约数

724. 约数

vector<int> devide(int x)
{
    for(int i=1;i<=x/i;i++)
    {
        if(x%i==0)
        {
            res.push_back(i);
            if(i!=x/i)  res.push_back(x/i);
        }
    }
}

约数的个数

给你一个数求约数时
1.如果你分解成质因数乘积后,约数个数等于各个质因数质数的指数的乘积

2.如果不是分解成质因数,题目给定了你某个连乘式=x,那么就需要计算所有出现的质因数的指数乘积,要用hash表,
因为连乘式中的项可能具有相同的质因数,要进行合并.两者做法是不一样的要注意
(即对于这种情况上面的质因数分解不适用)

//第二种情况
#include<iostream>
#include<unordered_map>
using namespace std;
const int MOD=1e9+7;
typedef long long ll;
unordered_map<int,int> primes;
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int x;
        cin>>x;
        for(int i=2;i<=x;i++) //如果x范围大的话应该换成另一种质因数分解的办法否则会tle
        {
            while(x%i==0)
            {
                primes[i]++;
                x/=i;
            }
        }
    }
    ll res=1;
    for(auto prime:primes)  res=res*(prime.second+1)%MOD;
    cout<<res;
}

约数之和

97. 约数之和

求最大公约数

808. 最大公约数

int gcd(int a,int b) //辗转相除法(欧几里得算法)求最大公约数
{
    return b? gcd(b,a%b):a;
}

公式法求最小公倍数(由最大公约数引入)

对于两个数而言最小公倍数最大公约数=两数相乘(！！！只适用于两个数),
如果想算多个数的最小公倍数,就拿第一个和第二个数算到的最小公倍数再和第三个数求最小公倍数

int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}

//对于两个数而言
int find_lcm(int a,int b)
{
    return a*b/gcd(a,b);
}

//对于一个数组b而言最小公倍数
int find_lcm(int b[],int n)
{
    int multi=1,lcm=1,gcd=1;  //相当于构造了一个哨兵元素b[-1]=1,跟b[0]进行求最小公倍数,构成递推
    for(int i=0;i<n;i++)
    {
        multi*=b[i];
        g=gcd(lcm,b[i]);
        lcm=multi/g;
        multi=lcm;
    }
    return lcm;
}

欧拉函数

单独求解某个数的欧拉函数值 O(sqrt(n))

原理:欧拉函数是对于积性函数(互质情况下)、如果n是质数的某一个次方，即 n = p^k (p为质数，k为大于等于1的整数)，则phi(n)=p^k*(1-1/p)
所以求某个数x的欧拉函数值,对其进行质因数分解,然后再将(质因数及其次方)看成一个整体,对其利用公式,求出最后phi(x)

LL phi(LL x)
{
    LL res=x;
    for(int i=2;i<=x/i;i++)
    {
        if(x%i==0)  res=res*(i-1)/i;
        while(x%i==0)   x/=i;
    }
    if(x>1) res=res*(x-1)/x;
    return res;
}

求某一段区间内的欧拉函数值

原理:结合线性筛法,如果是质数显然phi[i]=i-1

int primes[N],st[N];
int phi[N];
int cnt
void phi(int n)
{
    phi[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!st[i])  
        {
            primes[cnt++]=i;
            phi[i]=i-1;
        }
        for(int j=0;i*primes[j]<=n;j++)
        {
            st[i*primes[j]]=1;
            if(i%primes[j]==0)
            {
                //i与primes不互质无法使用积性
                //对i*primes[j]质因数分解,全都互质,使用积性
                //质因数分解后的结果对于原来的i来说,i乘上primes[j]后只是给primes[j]质因子的次数增加了1
                //根据公式phi(n)=p^k*(1-1/p),对(1-1/p)无影响,只会影响p^k
                //综上所述,对于整个phi[i*primes[j]],就是在phi[i]基础上乘了个primes[j]
                phi[i*primes[j]]=primes[j]*phi[i];、
                break;
            }
            phi[i*primes[j]]=(primes[j]-1)*phi[i];// i与primes[j]互质,符合欧拉函数的积性,phi[primes[j]]=primes[j]-1; primes[j]代表某一个质数
        }
    }
}