# Is there any way to split a number with multiplication of some prime number

I am looking for an algorithm which helps me split a number $N$ as such:

$$N=p_1^a p_2^b \cdots p_n^z$$

where $N$ is the given number, $p$ is prime numbers smallest to greatest, and $a,b,\cdots,z$ are the power over the prime.

e.g. $10 = 2^1 \cdot5^1, \quad 20 = 2^2 \cdot5^1$.

-
You can write decent-looking formulae with the help of $\LaTeX$. – FrenzY DT. Oct 24 '12 at 11:33

Following is a Java method to achieve that. The idea is to try to divide the input number $N$ by the same divisor repeatedly starting from $2$ and keep a counter of the number of successful division, then increment the divisor. We don't need to check primality of the divisors as once we have reduced

$N$ to $\frac{N}{p^k}$ where $p^k||N$, the later is no longer divisible by any multiple of $p$.

For example, $N=504$

$\frac{504}2=252, \frac{252}2=126, \frac{126}2=63\implies 2^3||504$

$4$ can not divide $\frac{504}{2^3}=63$

$\frac{63}3=21, \frac{21}3=7 \implies 3^2||504$

$5$ does not divide $7$

$6$ can not divide $\frac{504}{2^3\cdot 3^2}=7$

$\frac 7 7=1\implies 7^1||504$

So, $504=2^3\cdot 3^2\cdot7^1$

    private static String primtFactors(long datum) {

if (datum == 0)
return "0";

long datum2;

StringBuilder msg = new StringBuilder();

if (datum < 0) {
datum2 = -datum;
msg.append('-');
} else {
datum2 = datum;
}

if (datum2 == 1) {
msg.append('1');
} else {
for (long div = 2;;) {
int count = 0;
while (datum2 % div == 0) {
datum2 /= div;
count++;
}

if (count > 0) {
msg.append('(');
msg.append(div);
msg.append('^');
msg.append(count);
msg.append(')');
count = 0;
}

if (datum2 == 1)
break;

div++;
}
}

return msg.toString();

}


Sample output:

1=1

-1=-1

-72=-(2^3)(3^2)

0=0

105=(3^1)(5^1)(7^1)

72=(2^3)(3^2)

-

I think, you need the Sieve of Eratosthenes: suppose $M$ is the max. number you want to split, then build a boolean array (IsItPrime[n]), and go from $1$ to $\sqrt M$ and strike out the multiples and mark as prime the next unstriked element. (Detailed in wiki.)

Once you have found the primes and you have an array of them, the factorization is straightforward (the cycle for looking for divisors can be restricted to primes only).

-