#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
#define DEFAULT 5e5 + 5
#define int long long
#define i64 long long
#define i128 __int128
#define ull unsigned long long
#define db double
#define ldb long double
#define Arr std::vector
#define Ptn std::pair
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define popc(x) __builtin_popcountll(x)
#define clz(x) __builtin_clzll(x)
#define ctz(x) __builtin_ctzll(x)
#define chkmin(x, y) x = std::min(x, y)
#define chkmax(x, y) x = std::max(x, y)
#define FILE(x) freopen(x ".in", "r", stdin), freopen(x ".out", "w", stdout)
#define TEST(x) freopen(x ".in", "r", stdin), freopen("test.out", "w", stdout)
#define KEL(x) freopen(x ".in", "r", stdin), freopen("a.out", "w", stdout)
#define debug std::cout << "Running on " << __FUNCTION__ << ' ' << __LINE__ << std::endl;
#define fail assert(0);
#define lopzith return 0;
bool BeginPoint;
const int INF = 0x3f3f3f3f, llINF = 0x3f3f3f3f3f3f3f3f, P = 998244353;
const db eps = 1e-9;
const ull base = 13331;
const int N = 1e6 + 5;
int n, k, m, ans, A[N], vis[N];

inline int read()
{
    int w = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        w = (w << 3) + (w << 1) + (ch - 48);
        ch = getchar();
    }
    return w * f;
}

void init()
{
    for (int i = 2; i < N; i++)
    {
        if (vis[i]) continue;
        A[++m] = i;
        for (int p = i * i; p < N; p *= i) vis[p] = 1;
    }
}

bool EndPoint;
signed main()
{
    std::cerr << "Memory = " << fabs(&BeginPoint - &EndPoint) / 1048576.0 << "MB" << std::endl;

    n = read(), k = read();
    init();
    if (k == 1) return printf("%lld\n", n), 0;
    for (int i = 100; i >= std::max(3ll, k); i--)
    {
        auto chk = [&](int x)
        {
            i128 mul = 1;
            for (int j = 1; j <= i; j++)
            {
                mul *= A[x];
                if (mul > n) return false;
            } 
            return true;
        };
        int L = 1, R = m, aans = 0;
        while (L <= R)
        {
            int mid = (L + R) >> 1;
            if (chk(mid)) L = mid + 1, aans = mid;
            else R = mid - 1;
        }
        ans += aans;
    } ans++;
    if (k == 2)
    {
        n = sqrtl(n); int cnt = 0;
        for (int i = 1; i <= m; i++)
        {
            for (int p = A[i] * A[i]; p <= n; p *= A[i]) cnt++;
        }
        ans += (n - cnt);
        ans--;
    }
    printf("%lld\n", ans);

    std::cerr << "Time = " << (double)clock() / CLOCKS_PER_SEC << "s" << std::endl;
    lopzith
}