[[DP]] [[two pointers]]
link
A hint: There is near 3000000 numbers with maximal prime divisor <=100.
According to the hint, we can list all the passible numbers.
Then what we need to do is judge whether the number meets the condition or not.
We must make the cost smaller, so we can't simply mark all the prime divisors of each number.
We need to combine several divisors.
And, the maximal prime divisors must be selected (a conclusion).
We can do DP, by two pointers, in the sorted list.
#include<bits/stdc++.h>
using namespace std;
const int N=3000006;
int a[N],f[N],b[N],l,r,n,m,ans;
int main(){
int i,j;
scanf("%d%d%d",&l,&r,&n);
a[m++]=1;
for(i=2;i<=n;i++){
for(j=2;j<i;j++)if(i%j==0)goto E;
for(j=0;j<m;j++)if(1ll*a[j]*i<=r)a[m++]=a[j]*i;
E:;
}
sort(a,a+m);
memset(f,0x7f,sizeof(f));f[0]=0;
//DP and two_pointers
for(int i=2;i<n;i++)
for(int j=0,k=0;j<m;j++)
if(a[j]%i==0){
if(f[k]+1<f[j]){
f[j]=f[k]+1;
if(f[j]+i<=n)b[j]=1;
}
k++;
}
for(int i=0;i<m;i++)if(a[i]>=l&&b[i])ans++;
printf("%d",ans);
}