因为埃筛是把质数所有的倍数都过一遍，所以可以用来做模板 
#include <bits/stdc++.h>

using namespace std;

const int N=100005;
int fa[N],a,b,p,ans;
bool st[N];

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

int main(int argc, char** argv) {
	cin>>a>>b>>p;
	for(int i=1;i<=b;i++) fa[i]=i;
	
	for(int i=2;i<=b;i++){
		if(!st[i]){
			if(i>=p){//按题意因数大于p
				for(int j=i*2;j<=b;j+=i){
					st[j]=true;
					if(j-i>=a)//如果集合（j-i）在a~b内
                    fa[find(j)]=find(j-i);
				}
			}else{
				for(int j=i<<1;j<=b;j+=i){
					st[j]=true;
				}
			}
		}
	}
	for(int i=a;i<=b;i++)
		if(fa[i]==i) ans++;
	cout<<ans<<endl;
	return 0;
}