记录编号	234881	评测结果	AAAAAAAAAA
题目名称	整数合并	最终得分	100
用户昵称	Sky_miner	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2016-03-09 18:16:07	内存使用	0.77 MiB

#include <cstdio>
#include <cstring>
#include <cmath>
const int maxn = 100000 + 10;
int begin,end,p,prime = -1,cnt;
bool is_prime[maxn];
int fa[maxn];
int find(int x){
	int rt = x;
	while(fa[rt] != rt) rt=fa[rt];
	int temp;
	while(fa[x]!=rt) {
		temp=fa[x];
		fa[x]=rt;
		x=temp;
	}
	return rt;
}
void get_prime(int x){		//to find the prime 
	int t = sqrt(x)+1;
	for (int i=2;i<t;i++) {
		if (is_prime[i]) {
			for (int j=i*i;j<x;j+=i) {
				is_prime[j]=false;
			}
		}
	}
}
int main() {
	memset(is_prime,true,sizeof(is_prime));
	freopen("setb.in", "r", stdin);
	freopen("setb.out", "w", stdout);
	scanf("%d%d%d", &begin, &end, &p);
	get_prime(end);
	//find the first prime
	for (int i=p;i<=end;i++) {if (is_prime[i]){prime = i;break;}} // find the first prime
	if (prime == -1){printf("%d",end-begin);return 0;} // there is no prime
	for(int i=begin;i<=end;i++) fa[i]=i;
	bool key=true;
	int rx,ry;
	for (int i=prime;i<=end;i++) {
		if(is_prime[i]) {
			key = false;//haven't found
			int pos = i;
			while (pos < begin) pos+=i; // find the first position make i|pos  
			for(int j=pos;j<=end;j+=i){	// find the second position 
				if(!key){
					key = true;//sign that have found one
					rx = find(j);
				}
				else{//link one to 一堆 
					ry = find(j);
					if (rx != ry) fa[ry] = rx;
				}
			}
		}
	}
	for (int i=begin;i<=end;i++) if (fa[i] == i) cnt++;
	printf("%d",cnt); // ans~~~~ =_=|||||
	return 0;
}