Find exponent of prime $p$ in prime factorization of a number $x$

Question

Say we have a number $x$ such that $$ x = a^{r}.b^{s}.c^{t}.p^{u} $$ Is there a formula or method which can directly give me the exponent of a particular prime in this prime factorization.

For small $x$ calculating it is not a problem but when $x$ is of the order of $10^{8}$ finding the exponent of a particular prime becomes tough.

e.g. For $p$ it should give $u$, for $a$ it should give $r$ and so on.

If somehow $x$ can be represented as $\frac{a!}{b!}$ then also it can be done.

Answer 1

Given $x$ and $p$, just divide $x$ by $p$ repeatedly and count how many times it gives no remainder.

Answer 2

Here's a suggestion: Compute powers $p$, $p^2$, $p^4$, … $p^{2^n}$, … by repeated squaring (note that each of these is the square of the preceding one), until $p^{2^{n+1}}\nmid x$. Then repeat the procedure with $x_1=x/p^{2^n}$, and so forth, until you arrive at a number not divisible by $p$. Now $a=2^{n+1}+\cdots$, where $\cdots$ is the sum of powers of $2$ obtained in each subsequent step.

Answer 3

Expanding on FredAkalin's answer, we can write an algorithm in pseudocode as follows:

prime_exp(x,p):
    count = 0
    while x mod p is 0: (loop while x is exactly divisible by p)
        count += 1 (increase exponent value by 1)
        x = x / p (divide x by p)
    return count

We can run this on the number $364=2^2\times 7\times 13$:

prime_exp(364,2)

We first have

count = 0

We compute 364 mod 2 = 0

So now we have

count = 1
x = 364 / 2 = 182

We loop back round and compute 182 mod 2 = 0

So now we have

count = 2
x = 182 / 2 = 91

We loop back round again and compute 91 mod 2 = 1 so we exit the while loop

We therefore return the value of count = 2

We can see this is equal to the exponent of $2$ in the prime factorisation of $364$.