#include<bits/stdc++.h>
#define int __int128
using namespace std;
inline int read(){
	int s=0,w=1;char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())s=s*10+ch-'0';
	return s*w;
}
inline void write(int x){
	if(x<0){
		x=-x;
		putchar('-');
	}
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
map<int,bool> vis;
int n,k;
int sum=1;
signed main(){
	n=read(),k=read();
	if(k==1)return write(n),0;
	if(k>=60)return puts("1"),0;
	if(k>2||n<=1e12){
		for(int i=2;i<=1e6;++i){
			if(vis[i])continue;
			if(i>n)break;
			int t=i;
			bool flag=0;
			for(int j=2;j<=k;++j){
				if((__int128)t*i>n){flag=1;break;}
				if(t<=1e6)vis[t]=1;
				t*=i;
			}
			if(flag)break;
			for(int j=k;j<=59;++j){
				sum++;
				if(t<=1e6)vis[t]=1;
				if((__int128)t*i>n)break;
				t*=i;
			}
		}
		write(sum);
		return 0;
	}
	int chock=sqrt((unsigned long long)n-1),another=chock-1e6;
	for(int i=2;i<=1e6;++i){
		if(vis[i])continue;
		int t=i*i;
		for(int j=2;j<=59;++j){
			sum++;
			if(t<=1e6)vis[t]=1;
			if(t>1e6&&t<=chock)another--;
			if((__int128)t*i>n)break;
			t*=i;
		}
	}
	write(sum+another);
}