Decomposing an integer into primes raised to different powers The number $711000000$ can be written as $79^1 \times 2^6 \times 3^2 \times 5^6$. How are these numbers found? 
I guess the more general question is - given $n \in \mathbb Z $, how can you 'decompose' it into the product of primes raised to different powers?
 A: They are found by reversing the process that was used to come up with the number in the first place: you divide to reverse the multiplications. Presumably you chose these primes and powers of primes and multiplied them together to get this number. So you just divide out the primes or powers of primes.
Of course in some cases this is easier said than done. If you choose just two prime numbers large enough, you can multiply them easily enough but for someone else to divide out the two primes can take too much time to be practical (a concept of great practical use in cryptography).
Most of the answers so far mention trial division, a simple, humble method that works pretty well when the prime factors are mostly small and consecutive. This is important to remember: if $n = p_1 p_2 \ldots p_{\Omega(n)}$ is a composite number such that $p_1 \leq p_2 \leq \ldots \leq p_{\Omega(n)}$ ($\Omega(n)$ is a function that counts how many prime factors $n$ has) then $p_1 \leq \sqrt{n}$. If you have tried dividing $n$ by every prime up to $\sqrt{n}$ and found no prime factor, then $n$ is itself prime.
As a couple of the previous answers have suggested, you don't have to go through the primes below $\sqrt{n}$ in order. In your example of 711000000 it might make more sense to divide out the 2's and 5's first and then 3. But be sure to keep track of how often you divide by each prime: 711000000 divided by 2 is 355500000, and that divided by 2 is 177750000, then 88875000, 44437500, 22218750, 11109375 (six divisions by 2, hence the first exponent 6 in $2^6 \times 3^2 \times 5^6 \times 79$. At this point I'd rather divide by 5 than by 3. Yada, yada, yada, 395 divided by 5 is 79, which is prime.
Even a seemingly daunting number like 738629049682427904000000 is very quickly taken care of with trial division. A number like 738629049687284810748997 takes way too long with trial division. Fermat's difference of two squares method might work better in this case. Or you might even need something more sophisticated like Pollard's $\rho$ method or Pollard's $p - 1$ method.
A: There are a few different ways to factorize integers, but the simplest to understand (though not always the most efficient) is trial division. If the number is even, you divide it by $2$, giving you $355500000$. You keep dividing by $2$ until you get an odd number, in this case $11109375$. Then you go on to do the same thing with the next prime $3$, and so on and so forth. Of course if the number is prime to begin with, this is not such a good way to go about things.
A: Apart from the obvious criteria (divisibility by a power of $10$, divisibility by $5$), here are a few elementary facts one can use to speed up the trial division approach for relatively small $n$:


*

*The smallest prime factor of an integer $n$ is no greater than $\sqrt{n}$.(proof
)

*If the (base ten) digit sum of $n$ is divisible by $3$ (resp. $9$) then $n$ is divisible by $3$ (resp. $9$).

*If the last $k$ digits of $n$ form an integer that is divisible by $2^k$ (resp. $5^k$) then $n$ is divisible by $2^k$ (resp. $5^k$) ($k = 0,1,\ldots$).

*If the sum of every other digit of $n$ (starting from the first, leftmost digit) is divisible by $11$, then $n$ is divisible by $11$.


The first point should more or less be your go-to for any integer with $3$ digits or fewer, as there are only $11$ primes less than $\sqrt{1,000}$.
A: There do exist algorithms to do this, but they run in non-polynomial time (though with a quantum computer you would be able to do it in polynomial time).
There do exist some shortcuts for testing if a number $n$ is divisible by a prime $p$ for a few primes. For example:
If the last digit of a number is even, then the number is divisible by $2$.
If the sum of the digits of a number is divisible by $3$, then the number itself is divisible by $3$.
If the last digit of a number is either $5$ or a $0$, then the number is divisible by $5$
If you take a number and label every digit, after which you add up all the digits in a odd position and all the digits in an even position, the fact that their difference is divisible by 11 means that the whole number is divisible by 11 (Example: $796235$, $(7+6+3)-(9+2+5=)=0$ en $11\ |\ 0$ so $11\ |\ 796235$).
