关于质因数求最小公倍数

一般的最小公倍数我们可以直接相乘并除以这两个数的最大公倍数来求，但如果数字变多，记不太好求了 。

所以可以使用质数筛来求最小公倍数。

具体来看  当我们要求1~n 的最小公倍数时，有一条定理可以使用（我不会证）：

n个数的最小公倍数是这n个数里所有质因数的最高幂的乘积。

详见代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
ll mod=100000007;
const int M=100000000;
bool a[M+5];
int b[7000005];
int p=0,n;
ll ans=1;

void fun()
{
	a[0]=a[1]=1;
	for(register int i=2; i<=n; i++) 
	{
		if(!a[i])
		{
			b[p++]=i;
			for(ll k=i; k<=n; k*=i)
			{
				ans=ans*1ll*i%mod; 
			}
		}
		for(register int j=0; j<p&&i*b[j]<=M; j++)
		{
			a[i*b[j]]=1;
			if(i%b[j]==0)
				break;
		}
	}
}

int main()
{
	cin>>n;
	fun();
	cout<<ans<<endl;
	return 0;
}

其实就是在质数筛的时候顺便把这个质数的乘积给算出来。