数学知识

这是我在acwing上yxc的算法基础课上所做的笔记，内容基于课上所讲内容，代码模板都来自于acwing
www.acwing.com

质数

定义：只能被1和自己本身所整除的大于1的自然数

---

1. 判断素数的方法

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

暴力做法，对于每一个小于x的数都进行判定(时间复杂度O(n))

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

试除法优化
由于 x可以整除i， 所以x/i也可以被整除，约数的出现是成对出现的。所以我们只要枚举到较小的那一个就行. 时间复杂度为O(√n).
之所以结束条件不选择i <= sqrt(x)和i*i <= x, 每次循环计算sqrt(x)速度过慢, i*i有溢出风险

应用: 快速将一个数分解质因数

    vector<pair<int, int>> divide(int x)
    {
        vector<pair<int, int>> v; // 返回一个{底数， 指数}的数组
        for(int i=2;i <= x/i;i++)
        {
            if(x%i==0)
            {
                int cnt=0;
                while(x%i==0)
                {
                    cnt++;
                    x/=i;
                }
                v.push_back({i, cnt});
            }
        }
        if(x > 1) v.push_back({x, 1}); // 存在特殊情况，需要特判。

        return v;
    }

---

2. 筛质数
快速求1~n中质数的个数

    int prime(int n)
    {
        int prime[MAX], cnt=0;
        bool st[MAX]
        for(int i=2;i <= n;i++)
        {
            if(!st[i])
            {
                prime[cnt++]=i;
            }
            for(int j=i;j <= n;j+=i)
            {
                    st[j]=true;
            }
        }
    }

暴力做法，时间复杂度O(nlogn)
时间复杂度的计算:外层循环n， 内层对于(1/2+1/3+...+1/n)为调和级数，为log n；
缺点:对于一些数会被其约数中的合数和质数筛一遍(eg:18 会被2,3,6,9,18同时筛一遍)

    int prime(int n)
    {
        int prime[MAX], cnt=0;
        bool st[MAX]
        for(int i=2;i <= n;i++)
        {
            if(!st[i])
            {
                prime[cnt++]=i;
                for(int j=i;j <= n;j+=i)
                {
                    st[j]=true;
                }
            }
        }
        return cnt;
    }

埃式筛法(埃拉托斯特尼筛法)，时间复杂度O(nloglogn)；
改进:一个数只会被质数所筛去
缺点:还存在重复筛选的问题(eg:6会被2和3所筛去)

    int prime(int n)
    {
        int prime[MAX], cnt=0;
        bool st[MAX]
        for(int i=2;i <= 2;i++)
        {
            if(!st[i])
            {
                prime[cnt++]=i;
            }
            for(int j=0;prime[j] <= n/i;j++) //转换一下就是prime[j]*i <= n; 此时的数已经超过了n，没有了意义。
            {
                st[prime[j]*i]=true; 
                if(i%prime[j]==0) break; // 确保prime[j]*i只会被其最小的质因数所筛去
            }
        }
        return cnt;
    }

线性筛法, 故名思意时间复杂度为O(n)
优点:保证了一个合数只会被其的最小质因数所筛去。

…持续更新