记录编号	48479	评测结果	AAAAAAAAAA
题目名称	487.整数合并	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.015 s
提交时间	2012-11-05 20:40:02	内存使用	2.53 MiB

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100000 + 10;
int a, b, p, s = 0;
int f[N];
bool l[N] = {0}, v[N] = {0};
inline int ufs(int x) {
    return f[x] == x ? x : f[x] = ufs(f[x]);
}
int main() {
    freopen("setb.in", "r", stdin);
    freopen("setb.out", "w", stdout);
    scanf("%d %d %d", &a, &b, &p);
    for(int i=0; i<=b; i++)
        f[i] = i;
    for(int i=2; i<=b; i++) if(!v[i])
        for(int j=i+i; j<=b; j+=i) {
            v[j] = 1;
            if(i >= p) f[ufs(j)] = ufs(i);
        }
    for(int i=a; i<=b; i++) {
        int j = ufs(i);
        if(!l[j]) s += (l[j] = 1);
    } printf("%d\n", s);
    return 0;
}