relation between set of prime divisors of two positive integers

Question

How to tell in most efficient way that the set of prime divisors of a positive integer M is a superset of the set of prime divisors of another positive integer N where M and N are quite big numbers.

Those sets does not contain any duplicate.

Answer 1

Let $N_0=N$ and $M_0=M$ and $D_0=\gcd(M_0,N_0)$.

Then for $i\ge 1$, let $N_i=\frac{N_{i-1}}{D_{i-1}}$, $M_i=D_{i-1}$, and $D_i=\gcd(M_i,N_i)$.

If you get to $N_i=1$, then yes (prime divisors of $M$ are a superset of prime divisors of $N$); but if you get to $D_i=1$ with $N_i\ne 1$, then the answer is no.

Example:

$M=30, N=288$

$$\begin{array}{c|c|c} N&M&D\\ \hline 288&30&6\\ 48&6&6\\ 8&6&2\\ 4&2&2\\ 2&2&2\\ 1&2&1 \end{array}$$ Yes: prime factors of $30$ are a superset of prime factors of $288$.

Example:

$M=30, N=2520$ $$\begin{array}{c|c|c} N&M&D\\ \hline 2520&30&30\\ 84&30&6\\ 14&6&2\\ 7&2&1\\ \end{array}$$

Prime factors of $30$ are not a superset of prime factors of $2520$.

Since $N$ is at least cut in half at each step, this method seems quite efficient.