Prime factorization of $9095625$ by hand I'm interested to know if anyone knows of an efficient way to get the prime factorization of the following number by hand $9095625$.
 A: Since we're doing the prime factorization, you can just use the long division algorithm that you learned in grade school. Use the last digit as a clue for what to divide by. Remember that any number has a unique prime factorization, so always just divide by the smallest feasible prime.
In this case, we start by recognizing that the number is obviously divisible by $5$. Divide it by $5$, we get $1819125$. 
Divide by $5$ again. We get $363825$.
And again. We get $72765$.
And again. We get $14553$. The sum of the digits here is $18$, which is divisible by $3$, so this number is also divisible by $3$. Let's divide by $3$. We get $4851$. 
The sum of the digits of $4851$ is $18$ again, so let's divide by $3$ again. We get $1617$.
The sum of the digits of $1617$ is $15$, so we can go for one more round of dividing by $3$. We get $539$. 
To move swiftly from this step, we use a less-well-known divisibility trick. Dividing by $7$, we get $77$. 
Clearly the final prime factors of $77$ are $7$ and $11$. So there you go, the prime factorization is $3^3 \cdot 5^4 \cdot 7^2 \cdot 11$. 
On a whole, I wouldn't worry too much about problems like these. Doing prime factorizations by hand is pretty tedious, and it requires knowing all kinds of divisibility tricks. To me, this is like learning parlor tricks. Real mathematical problems lie in other domains.
Also, regarding your first sentence: in the computability-theoretic view, there is no efficient algorithm for finding the prime factorization of an integer. Finding such an algorithm would almost certainly be the discovery of the century. 
A: Last $4$ digits of the number, i.e. $5625$, is divisible by $625$ $\Longrightarrow$ $9095625$ is divisible by $625$( i.e., $5^4$),  giving the quotient as $14553$.
The sum of alternate digits of $14553 (1-4+5-5+3)$ is $0$ $\Longrightarrow$ the number is divisible by $11$, giving the quotient as $1323$.
Sum of digits of $1323$ is $9$ $\Longrightarrow$ the number is divisible by $9$, giving the result as $147$. 
Sum of $147$ $(1+4+7=12)$ is divisible by $3$ giving the quotient as $49$ which in turn is divisible by $7$. 
Combining them all gives $9095625= 5^4.11.3^3.7^2$
A: Some quick checks:


*

*The final digit of $9095625$ is $5$, so it is divisible by $5$. Repeatedly dividing by $5$ yields


$$9095625 = 5 \cdot 1819125 = 5^2 \cdot 363825 = 5^3 \cdot 72765 = 5^4 \cdot 14553$$


*

*The sum of the digits of $14553$ is $18$, so it is divisible by $9$. Repeatedly dividing by $3$ yields


$$14553 = 3 \cdot 4851 = 3^2 \cdot 1617 = 3^3 \cdot 539$$


*

*The next reasonable guess might be that $539$ is divisible by $7$... and indeed it is:


$$539 = 7 \cdot 77 = 7^2 \cdot 11$$


*

*...and $11$ is prime, so we're done.


In summary:
$$9095625 = 3^3 \cdot 5^4 \cdot 7^2 \cdot 11$$
