import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

  public static final int SIEVE_SIZE = 1_000_000;

  public static class MyScanner implements Closeable {
    BufferedReader br;
    StringTokenizer st;

    public MyScanner(String file) throws FileNotFoundException {
      br = new BufferedReader(new InputStreamReader(new FileInputStream(file)), 1 << 16);
    }

    String next() {
      while (st == null || !st.hasMoreElements()) {
        try {
          st = new StringTokenizer(br.readLine());
        } catch (IOException e) {
          e.printStackTrace();
        }
      }
      return st.nextToken();
    }

    int nextInt() {
      return Integer.parseInt(next());
    }

    long nextLong() {
      return Long.parseLong(next());
    }

    double nextDouble() {
      return Double.parseDouble(next());
    }

    String nextLine(){
      String str = "";
      try {
        str = br.readLine();
      } catch (IOException e) {
        e.printStackTrace();
      }
      return str;
    }

    @Override
    public void close() throws IOException {
      br.close();
    }
  }


  public static List<Long> sieve() {
    boolean[] sieve = new boolean[SIEVE_SIZE + 1];
    List<Long> primes = new ArrayList<>(1000);

    for (int i = 2; i <= SIEVE_SIZE; i++) {
      if (!sieve[i]) {
        primes.add((long)i);
        for (int j = i + i; j <= SIEVE_SIZE; j += i) {
          sieve[j] = true;
        }
      }
    }

    return primes;
  }

  public static List<Long> divisorsWithPrimes(long val, List<Long> primes) {
    int k = 0;

    List<Long> divs = new ArrayList<>();

    while (val > 1 && primes.get(k) * primes.get(k) <= val) {
      long d = primes.get(k);

      if (val % d == 0) {
        divs.add(d);
        do {
          val /= d;
        } while (val % d == 0);
      }

      k++;
    }

    if (val > 1) {
      divs.add(val);
    }

    return divs;
  }

  public static long check(long val, List<Long> divisors) {
    long sol = 0;

    for (int i = 1; i < (1 << divisors.size()); i++) {
      int nr = 0;
      long prod = 1;

      for (int j = 0; j < divisors.size(); j++) {
        if ( ((1 << j) & i) != 0) {
          nr++;
          prod *= divisors.get(j);
        }
      }

      if (nr % 2 == 1) {
        sol += (val / prod);
      } else {
        sol -= (val / prod);
      }
    }

    return val - sol;
  }

  public static void main(String[] args) throws IOException {

    try (MyScanner scanner = new MyScanner("frac.in");
        PrintWriter pw = new PrintWriter("frac.out")) {

      long N = scanner.nextLong();
      long P = scanner.nextLong();

      List<Long> primes = sieve();
      List<Long> divisors = divisorsWithPrimes(N, primes);

      long low = 0;
      long high = 100;
      long mid;

      long res = 1;

      while (low <= high) {
        mid = (low + high) >>> 1;

        long midP = check(mid, divisors);
        if (midP == P) {
          res = mid;
          break;
        } else if (midP < P) {
          low = mid + 1;
        } else {
          high = mid - 1;
        }
      }

      boolean ok = true;

      while (ok) {
        ok = false;
        for (int i = 0; i < divisors.size(); i++) {
          if (res % divisors.get(i) == 0) {
            ok = true;
            res--;
            break;
          }
        }
      }

      pw.println(res);
    }
  }
}