Prime Factorization of Integers
Prime Number A number is called Prime Number if and only if it has exactly 2 factors. Number “1” and the Number itself. i.e. Any number other than itself is not able to divide the number completely. If division is attempted, any other number will lead to non-zero remainder.
Prime Factorization Whenever a number is not Prime Number, it is called “Composite Number”. All composite number can be expressed as product of smaller prime number. The art (mathematics) of finding those factors is called “Prime Factorization”. You can use this website to find and share the prime factorization of any number smaller than 2 to the power 63. Simply share the link after you factorize the number. There are various algorithms available to factorize a number.
Trial Division This is the easiest of the methods. We divide the number by each odd number, and check if remainder is zero. We do this recursively till we keep getting factors. An useful trick to speed up this process is that we need to check only up-to square root of the number. Since if a number is a Composite Number, at least 1 of it’s factor has to be smaller than square root of the Number. Why? Basic algebra. If both factors are larger than square root, than the product itself will become larger than Number.
