AC了，求关注
原题链接：22750.集合
2024-06-30 10:49:32
发布于：浙江
0阅读
0回复
0点赞
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 100000 + 10;
int f[N],isPrime[N];
int find(int x)
{
return x == f[x] ? x : f[x] = find(f[x]);
}
void merge(int x,int y)
{
f[find(x)] = find(y);
}
//要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。
void sieve(int n)
{
for(int i = 0; i <= n; i++) isPrime[i] = 1;
isPrime[0] = isPrime[1] = 0;
for (int i = 2; i * i <= n; i++) {
if(isPrime[i])
for(int j = i * i; j <= n; j += i)
isPrime[j] = 0;
}
}
int main()
{
int a,b,p;
scanf("%d%d%d",&a,&b,&p);
sieve(b);
int cnt = b - a + 1;// 计算最初有几个集合
for(int i = a; i <= b; i++) f[i] = i;
for(int i = 2; i <= b; i++) {// 遍历b内的所有素数
if(isPrime[i] && i >= p) {
for(int j = i * 2; j <= b; j += i)
if(j - i >= a && find(j) != find(j - i)) {// 将当前的数与上一个数合并
merge(j,j - i);
cnt--;
}
}
}
printf("%d\n",cnt);
return 0;
}
这里空空如也
有帮助，赞一个