# Prime number decomposition

What is the fastest way to decompose the given number to prime numbers without using calculator?

Example : $$3575$$

What I do is :

$$3575 = 3 \times 10^3 + 5 \times 10^2 + 7 \times 10 + 5 = 3\times5^3\times2^3 + 5^2 \times 2^2 \times 5 + 7 \times 5 \times 2 + 5$$

But now I do not know how to effectively get rid of "$+$".

• This must be divisible by $5^2 = 25$ because divisibility by $25$ depends only on the last two digits (since multiples of $100$ are divisible by $25.$ Dividing it by $25$ you get $143$, and that's easy to factor (it's $11\times 13.$ Notice first that you need not check for divisibility by any prime numbers bigger than $\sqrt{3575}$ since it can have such factors only if it also has smaller prime factors (unless it's prime itself). If you don't know what $\sqrt{3575}$ is and so you don't know whether $25$ is bigger or smaller than $\sqrt{3575}, \text{ then } \ldots\ldots\qquad$ – Michael Hardy Mar 20 '17 at 19:31
• $\ldots\,$look at $3575 = 25\times143$ and observe that $25 < 143$ and concluded that $25$ is less than $\sqrt{3575}$ and $143$ is greater than $\sqrt{3575}.$ After that, you don't have to check $143$ for divisibility by any prime bigger than $\sqrt{143},$ so you only need to go up to $11.\qquad$ – Michael Hardy Mar 20 '17 at 19:36

By inspection, the final two digits of $75$ means $3575$ is divisible by $25=5^2$. Then the result of dividing out $25$ is $\frac{3500}{25} + \frac{75}{25}=4\times 35+3 = 143=12^2-1 = 11\cdot 13$, giving $3575 = 5^2\cdot11\cdot13$
The fastest way in general is by some "fast" algorithm, whether by computer, or by hand. There is no shortcut in general. There are many Integer factorization algorithms, but the running time is, even for the general number theory sieve, given by $${\displaystyle O\left(\exp {\sqrt[{3}]{{\frac {64}{9}}b(\log b)^{2}}}\right)}$$ for a $b$-bit number $n$. For $n=3575$ we obtain $5^2\cdot 11\cdot 13$. Here we could first try small prime divisors.
$$3600 - 25 = 60^2 - 5^2 = (60 + 5) (60 - 5) = 65 \cdot 55$$ Then we see $65 = 5 \cdot 13$ and $55 = 5 \cdot 11$
This is usually called Fermat factorization. Start with the first square larger than the number, see if the difference is a square. If that does not work take the square just larger than that. To save time, we can rule out some squares since the difference cannot be $3 \pmod 4$ or $2 \pmod 4.$ In this case, $61^2 - 3575 = 146 \equiv 2 \pmod 4$ cannot be a square. We would jump to $62^2 - 3575,$ then $64^2 - 3575.$ However, the first time worked.
If I gave you $9991$ the next larger square would be $10000$ and $10000 - 9991 = 9,$ so $9991 = (100 +3)(100-3) = 103 \cdot 97$