#include<bits/stdc++.h>
using namespace std;
int head[100005];
bool e[100005];
int yq[100005];
int a,b,p;
int ans,en;
int find(int x) {
	return head[x] == x?x:head[x] = find(head[x]);
}
bool pd(int x,int y) {
	for(int i = 1;i <= en;i++) {
		if(x % yq[i] == 0 and y % yq[i] == 0 and yq[i] >= p) {
			return 1;
		}
	}
	return 0;
}
int main() {
	scanf("%d%d%d",&a,&b,&p);
   //筛质数
	for(int i = 2;i <= b;i++) {
		if(e[i]) {
			continue;
		}
		yq[++en] = i;
		for(long long j = (long long) i * i;j <= b;j+=i) {
			e[j] = 1;
		}
	}
	ans = b - a + 1;
	for(int i = a;i <= b;i++) {
		head[i] = i;
	}
    //暴力枚举
	for(int i = a + 1;i <= b;i++) {
		for(int j = a;j <= i;j++) {
			if(find(i) != find(j)) {
				if(pd(i,j)) {
					head[find(j)] = find(i);
					ans--;
				}
			}
		}
	}
	printf("%d",ans);
}

提交记录