Prime number decomposition

Question

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

Answer 1

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$

Answer 2

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.

Answer 3

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