自动搬运

查看原文

来自洛谷，原作者为

	ouuan 如果奇迹有颜色的话，那么其中之一必是橙色的吧。

搬运于2025-08-24 21:27:11，当前版本为作者最后更新于2018-07-14 12:44:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

大家都是先筛素数再合并？其实用埃氏筛法的话筛的同时就可以合并了，因为每个数都被它的所有质因数各筛了一遍，直接在用每个质因数筛的时候把被筛掉的数合并就好了。

#include <iostream>

using namespace std;

int find(int x);

int f[100010],a,b,p,ans;
bool np[100010];

int main()
{
	int i,j;
	
	cin>>a>>b>>p;
	
	ans=b-a+1; //将答案初始化为a~b间数的个数，每合并一次减1就可以了
	
	for (i=a;i<=b;++i)
	{
		f[i]=i;
	}
	
	for (i=2;i<=b;++i) //埃氏筛
	{
		if (!np[i])
		{
			if (i>=p) //如果当前质数大于p才合并
			{
				for (j=i*2;j<=b;j+=i)
				{
					np[j]=true;
					if (j-i>=a&&find(j)!=find(j-i)) //将当前被筛的数与上一个被筛的数合并（第一个被筛的数和质因数本身合并），注意这两个数都要在a~b之间才合并
					{
						f[find(j)]=find(j-i);
						--ans;
					}
				}
			}
			else
			{
				for (j=i*2;j<=b;j+=i)
				{
					np[j]=true;
				}
			}
		}
	}
	
	cout<<ans;
	
	return 0;
} 

int find(int x)
{
	return x==f[x]?x:f[x]=find(f[x]);
}