https://www.luogu.com.cn/problem/P1621

//P1621 集合
/*
预处理，筛法，从p开始，枚举大于p的质数

枚举到的数，集合合并 
 
*/

#include<bits/stdc++.h>
using namespace std;
int a, b, p, ans;
const int maxn  = 1e5 + 5;
int fa[maxn];
bool vis[maxn];
bool make[maxn];

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

void merge(int x, int y){
	x = get(x);
	y = get(y);
	if (x != y){
		fa[y] = x;
	}
}

bool zs(int x){
	if(x % 2== 0) return 0;
	if (x == 2) return 1;
	for (int i = 3; i <= sqrt(x);i+=2){
		if(x % i == 0){
			return 0;
		}
	}
	return 1;
}

int main () {
	cin >> a >> b >> p;
	for (int i = 1;i <= b; i++){
		fa[i] = i;
	}
	
	//从p开始枚举
	for (int i = p; i <= b; i++){
		if(vis[i]) continue;
		if ( zs(i) ) {//是质数 
			vis[i] = 1;
			for (int j = 1; j * i <= b; j++){
				vis[j*i] = 1;
				if (j * i < a){
					continue;
				}
				//合并
				if (get(i) != get(j * i) ){
					merge(i, j*i);
				}
			}
		}
	}
	for (int i = a; i <= b; i++){
		if(!make[get(i)]){
			make[get(i)] = 1;
			ans++;
		}
	} 
	cout << ans;
}