#include <bits/stdc++.h>

FILE *in = fopen("frac.in", "r"), *out = fopen("frac.out", "w") ;

std::vector<long long> getPrimeDivisors(long long B) {
        std::vector<long long> ret ;
        for (long long divisor(2) ; divisor * divisor <= B ; ++ divisor) {
                if (B % divisor == 0) {
                        ret.push_back(divisor) ;
                        for ( ; B % divisor == 0 ; B /= divisor) ;
                }
        }
        if (B > 1) {
                ret.push_back(B) ;
        }
        return ret ;
}

long long compute(long long state, long long divisors, std::vector<long long> primeDivisors, long long limit) {
        long long numberSubSets = __builtin_popcount(state) ;
        long long setCoef = ((numberSubSets % 2) ? 1 : -1) ;
        long long currentDivisor(1) ;
        for (long long i = 0 ; i < divisors ; ++ i) {
                if ((state >> i) & 1) {
                        limit /= primeDivisors[i] ;
                }
        }
        return limit * setCoef ;
}

long long solve(long long A, long long B, std::vector<long long> primeDivisors) {
        long long divisors(primeDivisors.size()) ;
        long long ret(0) ;
        for (long long state(1) ; state < (1 << divisors) ; ++ state) {
                ret += compute(state, divisors, primeDivisors, A) ;
        }
        return ret ;
}

int main() {
        int tests ;
        long long A, B ;
        fscanf(in, "%lld %lld", &A, &B) ;
        std::vector<long long> primeDivisors = getPrimeDivisors(A) ;
        long long ans(0) ;
        for (long long step = (1LL << 5) ; step ; step >>= 1) {
                if (step + ans - solve(step + ans, A, primeDivisors) < B) {
                        ans |= step ;
                }
        }
        fprintf(out, "%lld", ans + 1) ;
}