Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$.

share|improve this question
    
You can write decent-looking formulae with the help of $\LaTeX$. –  FrenzY DT. Oct 24 '12 at 11:33
add comment

2 Answers

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).

share|improve this answer
add comment

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)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.