C++ :

#include<bits/stdc++.h>
#define N 100010 
using namespace std;
int a,b,x,ans,cnt;
int fa[N],notp[N],p[N];

//路径压缩的查找算法，找出x的根 
int find(int x){
	//x的父直接指向x的根 
	return x == fa[x]?x:fa[x] = find(fa[x]);
} 

//集合合并 
void merge(int x,int y){
	int fx = find(x);
	int fy = find(y);
	if(fx != fy) fa[fx] = fy;
}

//非素数筛选 
void getprime(){
	notp[1] = 1;//1不是素数
	//筛选2~b范围内的非素数 
	for(int i = 2;i <= b;i++){
		if(notp[i]) continue; //如果i已经是非素数了
		for(int j = 2*i;j <= b;j=j+i){
			notp[j] = 1;
		} 
	} 
	
	//将大于x~b之间的素数找出来
	for(int i = x;i <= b;i++){
		if(!notp[i]){
			cnt++;
			p[cnt] = i;
		}
	} 
}

int main(){
	cin>>a>>b>>x;
	//并查集初始化
	for(int i = a;i <= b;i++) fa[i] = i;
	getprime();//筛选素数 
	
	//遍历x~b之间所有的素数 
	for(int i = 1;i <= cnt;i++){
		for(int j = 2;j * p[i] <= b;j++){
			//两个数有>=x的质因子 
			if(j * p[i] >= a && (j-1) * p[i] >= a){
				merge(j*p[i],(j-1)*p[i]);
			}
		}
	} 
	
	//看有几个集合
	for(int i = a;i <= b;i++){
		if(fa[i]==i) ans++;
	} 
	cout<<ans;
	return 0;
}