#include <cstdio>
#include <unordered_set>
using namespace std;
long long n, k, q;
unordered_set<long long> p;
long long P(long long x, long long k)
{
	long long q = 1;
	while(k--)
		if((q *= x) > n)
			return -1;
	return q;
}
long long S(long long x)
{
	long long l = 0, r = 2e9, m;
	while(l <= r)
	{
		m = l + r >> 1;
		if(m * m <= x)
			l = m + 1;
		else r = m - 1;
	}
	return r;
}
int main()
{
	scanf("%lld%lld", &n, &k);
	if(k == 1)
		q = n;
	if(k == 2)
	{
		q = S(n);
		for(long long i = 3;~P(2, i);++i)
			for(long long j = 1, x, s;~(x = P(j, i));++j)
				s = S(x), q += s * s != x && p.find(x) == p.end(), p.insert(x);
	}
	if(k > 2)
	{
		for(long long i = k;~P(2, i);++i)
			for(long long j = 1, x;~(x = P(j, i));++j)
				q += p.find(x) == p.end(), p.insert(x);
	}
	printf("%lld", q);
	fclose(stdin);fclose(stdout);
	return 0;
}

95 pts