求助问题在哪?
查看原帖
求助问题在哪?
465246
GTY_very_like_it楼主2022/11/13 15:55
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6;

int l,r,p;
int cnt;
int a[N];
int f[N];
int vis[N];

void judge(){
	vis[1] = 1;
	for(int i = 2; i <= N; i++){
		if(!vis[i]){
			for(int j = i * 2; j <= N; j += i){
				vis[j] = 1;
			}
		}
	}
	for(int i = p; i <= r; i++){
		if(!vis[i]) a[++cnt] = i;
	}
}

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

void merge(int x, int y){
	x = find(x);
	y = find(y);
	if(x != y) f[min(x,y)] = max(x,y);
}

int main(){
	cin >> l >> r >> p;
	judge();
	for(int i = l; i <= r; i++) f[i] = i;
	for(int i = 1; i <= cnt; i++){
		int t = a[i];
		while(t < l){
			t += a[i];
		}
		while(t <= r){
			merge(t,a[i]);
			t += a[i];
		}
	}
	
	int ans = 0;
	for(int i = l; i <= r; i++){
		if(find(i) == i) ans++,cout << i << endl;
	}
	cout << ans;
	
	return 0;
}

2022/11/13 15:55
加载中...