JZTXT

数论基础1(质数判断,分解质因数,筛法,优化筛法,约数,约数个数,约数之和)

发布时间 2023-03-23 23:22:40作者: 风乐

模板:

//质数判定--试除法 
//朴素 O(N)
bool is_prime(int n)
{
	if(n<2)return false;
	for(int i=2;i<n;i++)
	{
		if(n%i==0)return false;
	 } 
	return true;
} 

//朴素优化 O(sqrt(N)) 
bool is_prime(int n)
{
	if(n<2)return false;
	for(int i=2;i<=n/i;i++)//不推荐写sqrt(N)，每次循环都会执行sqrt，比较慢 
	//也不推荐i*i<=n，当i较大时,存在溢出风险，变成负数 
	{
		if(n%i==0)return false;
	} 
	return true;
} 

//分解质因数--试除法
//原理:算数基本定理:一个数由多个质数的乘积组成
//从小到大枚举所有数,包括合数和质数，去判断是否是n的约数
//时间复杂度,最好情况：当数据量N=2^K,由于i从2开始，那么一开始就会除k次2,最后n=1，那么就是O(logn) 
//最坏就是 枚举完，O(sqrt(n)) 
void divide(int n)
{ 
	//n中最多只包含一个大于sqrt(n)的质数
	//其他的质因子必定小于sqrt(n) ,故可以i<=n/i 
	//先枚举小于sqrt(n)的数，除干净后，剩下的数就是大于sqrt(n)的质因子 
	for(int i=2;i<=n/i;i++)
	{
		if(n%i==0)//n是i的倍数，且2~i-1之间不存在n的因子 
		//但是i却可以整除n，因此此时i一定是质数 
		{
			int s=0;
			while(n%i==0) 
			{
				n/=i;
				s++;
			}
			cout << i << ' ' << s << endl;
		}
	}
	//剩余的数大于1，那么这个数就是大于sqrt(n)的唯一的质因数
	if( n > 1)cout << n << 1  << endl; 
}

//筛法
//朴素 O(nlogn)
int primes[N],cnt;
bool st[N];
void get_primes(int n)
{
	for(int i=2;i<=n;i++)//从2开始枚举
	{
		if(st[i]==false)//找到素数,就加入primes中
		{
			primes[cnt++]=i;
		}
		//无论是不是素数都将其倍数都筛掉
		for(int j=i+i;j<=n;j+=i)st[j]=true;
	}
}

//埃氏筛法
//筛法O(nloglogn),或者粗略的认为O(n)
int primes[N],cnt;
bool st[N];
void get_primes(int n)
{
	for(int i=2;i<=n;i++)//从2开始枚举
	{
		if(st[i]==false)//找到素数,就加入primes中
		{
			primes[cnt++]=i;
			//将质数其倍数都筛掉,因为质数的倍数必定是合数,因此可以放在判断里面
			//算数基本定理:合数能通过比他小的质数表示出来
			for(int j=i+i;j<=n;j+=i)st[j]=true;
		}
	}
}


//线性筛法
//1e6的数据和埃筛效率差不多,1e7比埃筛快一倍
//n只会被n的最小质因子筛掉
int primes[N],cnt;
bool st[N];
void get_primes(int n)
{
	for(int i=2;i<=n;i++)//从2开始枚举所有数
	{
		//找到素数,就加入primes中
		if(st[i]==false)primes[cnt++]=i;
		//从小到大枚举所有质数
		for(int j = 0; primes[j] <= n / i;j ++ )//也可以primes[j]*i<=n,表示枚举所有以primes[j]为最小质因子的数
		{
			st[primes[j]*i]=true;//每次把质数和i的乘积筛掉
			if(i % primes[j]==0)break; //primes[j]一定是i的最小质因子
			//因为primes[j]是从小到大枚举的,那么一旦primes[j]可以整除i,它就是最小的质因数
			//因此primes[j]一定是primes[j]*i最小质因子
		}
		//核心:每一个数,不管是合数还是质数,都只会被它的最小质因子筛唯一一次,所以是线性的
	}
}


//求约数--试除法
//朴素->优化 O(sqrt(n))
vector<int> get_divisors(int n)
{
	vector<int> res;
	
	for(int i=1;i<=n/i;i++)//朴素就是i<n
	{
		if(n%i==0)
		{
			res.push_back(i);
			//i为约数,那么n/i也是n的约数
			if(i != n/i )res.push_back(n/i);//有可能n=i*i,为了防止重复就得判断
		}
	}
	sort(res.gegin(),res.end());
	return res;
}

 试除法求质数
https://www.acwing.com/problem/content/description/868/

#include<iostream>
using namespace std;
long long a;
int n;

bool is_prime(int n)
{
	if(n<2)return false;
	for(int i=2;i<=n/i;i++)//不推荐写sqrt(N)，每次循环都会执行sqrt，比较慢 
	//也不推荐i*i<=n，当i较大时,存在溢出风险，变成负数 
	{
		if(n%i==0)return false;
	} 
	return true;
} 
int main()
{
    cin >> n;
    while(n--)
    {
        cin >> a;
        if(is_prime(a))cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

分解质因数:
https://www.acwing.com/problem/content/869/

#include<iostream>
using namespace std;
int m;
int a;

void divide(int n)
{ 
	//n中最多只包含一个大于sqrt(n)的质数
	//其他的质因子必定小于sqrt(n) ,故可以i<=n/i 
	for(int i=2;i<=n/i;i++)
	{
		if(n%i==0)//n是i的倍数，且2~i-1之间不存在n的因子 
		//但是i却可以整除n，因此此时i一定是质数 
		{
			int s=0;
			while(n%i==0) 
			{
				n/=i;
				s++;
			}
			cout << i << ' ' << s << endl;
		}
	}
	if( n > 1)cout << n << ' ' << 1 << endl;
	cout << endl;
}

int main()
{
    cin >> m;
    while(m--)
    {
        cin >> a;
        divide(a);
    }
    return 0;
}

筛质数:
https://www.acwing.com/problem/content/description/870/
朴素:

#include<iostream>
using namespace std;
const int N = 1e6+10;
int num;
int primes[N],cnt;
bool st[N];
void get_primes(int n)
{
	for(int i=2;i<=n;i++)//从2开始枚举
	{
		if(st[i]==false)//找到素数,就加入primes中
		{
			primes[cnt++]=i;
		}
		//无论是不是素数都将其倍数都筛掉
		for(int j=i+i;j<=n;j+=i)st[j]=true;
	}
}
int main()
{
    cin >> num;
    get_primes(num);
    cout << cnt << endl;

}

埃筛优化:
埃筛会重复筛一些数

#include<iostream>
using namespace std;
const int N = 1e6+10;
int num;
int primes[N],cnt;
bool st[N];
void get_primes(int n)
{
	for(int i=2;i<=n;i++)//从2开始枚举
	{
		if(st[i]==false)//找到素数,就加入primes中
		{
			primes[cnt++]=i;
			//将质数其倍数都筛掉,因为质数的倍数必定是合数
			//算数基本定理:合数能通过比他小的质数表示出来
			for(int j=i+i;j<=n;j+=i)st[j]=true;
		}
	}
}
int main()
{
    cin >> num;
    get_primes(num);
    cout << cnt << endl;

}

线性筛:

#include<iostream>
using namespace std;
const int N = 1e6+10;
int num;
int primes[N],cnt;
bool st[N];
void get_primes(int n)
{
	for(int i=2;i<=n;i++)//从2开始枚举所有数
	{
		//找到素数,就加入primes中
		if(st[i]==false)primes[cnt++]=i;
		//从小到大枚举所有质数
		for(int j = 0; primes[j] <= n / i;j ++ )//也可以primes[j]*i<=n,表示枚举所有以primes[j]为最小质因子的数
		{
			st[primes[j]*i]=true;//每次把质数和i的乘积筛掉
			if(i % primes[j]==0)break; //primes[j]一定是i的最小质因子
			//因为primes[j]是从小到大枚举的,那么一旦primes[j]可以整除i,它就是最小的质因数
			//因此primes[j]一定是primes[j]*i最小质因子
		}
		//每一个数,不管是合数还是质数,都只会被它的最小质因子筛唯一一次,所以是线性的
	}
}
int main()
{
    cin >> num;
    get_primes(num);
    cout << cnt << endl;

}

求约数--试除法
https://www.acwing.com/problem/content/871/

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int n,a;

vector<int> get_divisors(int n)
{
	vector<int> res;
	
	for(int i=1;i<=n/i;i++)//朴素就是i<n
	{
		if(n%i==0)
		{
			res.push_back(i);
			if(i != n/i )res.push_back(n/i);//有可能n=i*i,为了防止重复就得判断
		}
	}
	sort(res.begin(),res.end());
	return res;
}
int main()
{
    cin >> n;
    while(n--)
    {
        cin >> a;
        vector<int>res = get_divisors(a);
        for(auto i:res)
            cout << i << ' ';
        cout << endl;
    }
}


求约数个数
https://www.acwing.com/problem/content/872/

对于数N,根据算数基本定理可以分解为d这样的形式的若干数相乘
N的任何一个约数都长成d这样的形式,其中每一个d的p的指数都不同,那么其约数d值也就不同,算数基本定理可以得到每个数的因式分解是不同的,因式分解不一样,两个数的值就不一样
pi的指数有α+1种选法,根据排列组合,总共有(α1+1)*(α2+1)*(α3+1)*.......(αk+1)种选法,即为N的约数的个数

#include<iostream>
#include<unordered_map>
using namespace std;
typedef long long LL;
const int mod = 1e9+7;
LL res=1;
int x,n;

int main()
{
    unordered_map<int,int> primes;
    cin >> n;
    while(n--)
    {
        cin >> x;
        //首先先分解质因数
        for(int i=2;i<=x/i;i++)
        {
            while(x % i == 0)
            {
                x /= i;
                primes[i]++;//把所有质因子的指数累加起来
            }
        }
        if(x>1)primes[x]++;//大于sqrt(x)的质因子
    }
    for(auto prime:primes)res=res*(prime.second+1) % mod;
    cout << res << endl;
}

求约数之和
https://www.acwing.com/problem/content/873/

把约数之和的式子展开,就有许多的扩号这样的形式
每一个括号里都是p1^β1*p2^β2...pk^βk的形式,且每一个括号里面形式都不一样
根据算数基本定理,这样的形式,每一个括号,实际上都是一个约数
那么这么多括号之和就是约数的和

#include<iostream>
#include<cmath>
#include<unordered_map>
using namespace std;
typedef long long LL;
const int mod = 1e9+7;
LL res=1;
int x,n;

int main()
{
    unordered_map<int,int> primes;
    cin >> n;
    while(n--)
    {
        cin >> x;
        for(int i=2;i<=x/i;i++)
        {
            while(x % i == 0)
            {
                x /= i;
                primes[i]++;//把所有质因子的指数累加起来
            }
        }
        if(x>1)primes[x]++;//大于sqrt(x)的质因子
    }
    
    for(auto prime:primes)
    {
        int p = prime.first;
        int a = prime.second;
        LL t = 1;
        while(a--)t = (t*p+1) % mod;//令t=pt+1,执行2次,那么t = p^2+p+1,执行a次就有p^a+p^a-1+,,,+p^0
        res=res*t%mod;
    }
    cout << res << endl;
}

欧几里得算法(辗转相除法)

有一个性质:a是d的约数,b也是d的约数,那么有x倍的a+y倍的b为d的约数,x,y为任意
可以证明a,b的最大公约数是b,a mod b的最大公约数,反之也成立
https://www.acwing.com/problem/content/874/

#include<iostream>
using namespace std;
const int N = 1e5+10;
int x,y,n;
int gcd(int a,int b)
{
    return b ? gcd(b,a%b):a;
}

int main()
{
    cin >> n;
    for(int i=0;i<n;i++)
    {
        cin >> x >> y;
        cout << gcd(x,y) << endl;
    }
    return 0;
}