记录编号	601959	评测结果	AAAAAAAAAA
题目名称	487.整数合并	最终得分	100
用户昵称	LikableP	是否通过	通过
代码语言	C++	运行时间	0.025 s
提交时间	2025-06-29 19:10:06	内存使用	1.73 MiB

#include <cstdio>

const int MAXN = 1e5 + 10;

bool vis[MAXN];
int fa[MAXN];
int a, b, p;
int ans;

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

int main() {
  freopen("setb.in", "r", stdin);
  freopen("setb.out", "w", stdout);
  scanf("%d %d %d", &a, &b, &p);
  ans = b - a + 1;
  for (int i = a; i <= b; ++i) {
    fa[i] = i;
  }
  for (int i = 2; i <= b; ++i) {
    if (!vis[i]) {
      for (int j = i + i; j <= b; j += i) {
        vis[j] = 1;
        if (i >= p && j - i >= a && find(j) != find(j - i)) {
          ans--;
          fa[find(j)] = find(j - i);
        }
      }
    }
  }
  printf("%d\n", ans);
  return 0;
}