from bisect import bisect_right from collections import deque def main(): import sys input = sys.stdin.read().split() n = int(input[0]) p = int(input[1]) if p == 1: print(1) return # Sieve of Eratosthenes to generate primes up to n def sieve(max_num): if max_num < 2: return [] sieve = [True] * (max_num + 1) sieve[0] = sieve[1] = False for i in range(2, int(max_num ** 0.5) + 1): if sieve[i]: sieve[i*i : max_num + 1 : i] = [False] * len(sieve[i*i : max_num + 1 : i]) primes = [i for i, is_prime in enumerate(sieve) if is_prime] return primes primes = sieve(n) if not primes: print(1 if p == 1 else 0) return # Factorize p to get initial primes def factorize(num): factors = {} if num == 1: return factors i = 2 while i * i <= num: while num % i == 0: factors[i] = factors.get(i, 0) + 1 num = num // i i += 1 if num > 1: factors[num] = 1 return factors.keys() initial_factors = factorize(p) primes_set = set(primes) initial_primes = [prime for prime in initial_factors if prime in primes_set] if not initial_primes: print(1) return primes_sorted = primes visited = set(initial_primes) queue = deque(initial_primes) while queue: current_p = queue.popleft() max_q = n // current_p idx = bisect_right(primes_sorted, max_q) for q in primes_sorted[:idx]: if q not in visited: visited.add(q) queue.append(q) # Mark all multiples of visited primes marked = [False] * (n + 1) for prime in visited: for multiple in range(prime, n + 1, prime): marked[multiple] = True count = sum(marked) print(count) if __name__ == '__main__': main()