#include <iostream>
#include <fstream>
#include <bitset>
#include <cmath>

using namespace std;

ifstream fin("zero2.in");
ofstream fout("zero2.out");

const int NMax = 1e5;
const int PMax = 1e4;
const int INF = 1e9;

int k;
int primes[PMax];

bitset < NMax > ciur;

inline void eratos(){
    primes[++k] = 2;
    for(int i = 3; i < NMax; i += 2){
        if(!ciur[i]){
            primes[++k] = i;
            for(int j = 2 * i; j < NMax; j += i){
                ciur[j] = 1;
            }
        }
    }
}

int main(){
    int t = 10;
    eratos();
    long long int n, b, cnt, ans;
    while(t--){
        fin >> n >> b;
        ans = INF;
        for(int i = 1; primes[i] <= b && i <= k; i++){
            if(b % primes[i] == 0){
                cnt = 0;
                while(b % primes[i] == 0){
                    b /= primes[i];
                    cnt++;
                }
                if(cnt != 0){
                    ans = min(ans, max(0, 1LL * (n - primes[i] + 1) / cnt));
                }
            }
        }
        fout << ans << "\n";
    }
    return 0;
}