#include <bitset>
#include <fstream>
#include <vector>
using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");
const long long kMax = 1e6 + 5;
long long A, B;
bitset<kMax> isPrime;
vector<int> primeList, divB;

void sieve()
{
	isPrime.set();
	isPrime[0] = isPrime[1] = false;

	primeList.push_back(2);
	for (long long i = 4; i < kMax; i += 2)
		isPrime[i] = false;

	for (long long i = 3; i < kMax; i += 2)
	{
		if (isPrime[i])
		{
			primeList.push_back(i);
			for (long long j = i * i; j < kMax; j += i)
				isPrime[j] = false;
		}
	}
}


int main()
{
	sieve();
	fin >> A >> B;

	int cb = B;
	for (size_t i = 0; i < primeList.size() && cb != 1; ++i)
	{
		if (!(cb % primeList[i]))
		{
			divB.push_back(primeList[i]);
			while (!(cb % primeList[i]))
				cb /= primeList[i];
		}
	}

	long long notInSet = 0;
	int sz = divB.size(), pwr = (1 << sz);
    for (int bitMask = 1; bitMask < pwr; ++bitMask)
	{
		int bitsSet = 0;
		long long factor = 1;
        for (int i = 0; i < sz; ++i)
		{
			if (bitMask & (1 << i))
			{
				++bitsSet;
                factor *= divB[i];
			}
		}

		if (bitsSet % 2)
			notInSet += (A / factor);
		else
			notInSet -= (A / factor);
	}

	fout << A - notInSet << '\n';
	return 0;
}