Factorise A number in to product of two numbers

Question

I would like to know what is the quickest way to factorise large number ( more than 1000) in to two numbers

For Example 2669

2669 is 17 * 157 how can I find this ?

Answer 1

The factorisation of big numbers is a hard problem, there is no efficient algorithm known that can find a factor of a number in polynomial time. This fact is even used in public key cryptography, where big numbers are used as public keys and their factors as private keys.

But these things only apply for really big numbers, with hundreds of digits. For smaller numbers like the one you said, I would either ask wolframalpha or check if they are divisible by prime numbers up to their square root.

In you example 2669, you can check if it is divisible by $2,3,5,7,11,13,\ldots,47$. If you didn't find a factor until then, it is a prime number.

Answer 2

Trial division, as in Lief's answer is the most reliable method, though it soon gets laborious. In this case, you might notice that $2669 = 50^{2}+13^{2} = (50+13i)(50-13i)$. If you were really observant, you might see that working (mod $17$), $50+13i = -(4i+1),$ which is a factor of $17$ in the Gaussian integers $\mathbb{Z}[i].$ Hence $50+13i = 17(3+i) -(4i+1) = (4i+1)[(1-4i)(3+i) - 1] = (4i+1)(6-11i).$ Hence also $50-13i = (1-4i)(6+11i),$ and multiplying these two complex conjugate expressions together gives $2669 = 17 \times 157.$ This happened too work because it was noticed that $2669$ is a sum of two integer squares.