Captain P. wrote:
where i is an integer that increases each time the while is run, as long as (i <= input).
Since the input is the product of two elements the sum of those two elements will always be smaller than (or equal to) 2*sqrt(input). Basically this means that when you do a run from 1 till input, you will be repeating steps after the square root of the input.
For example, the number 24 :
24 % 1 = 0 -> 1 is a valid element, 24 / 1 = 24
24 % 2 = 0 -> 2 is a valid element, 24 / 2 = 12
24 % 3 = 0 -> 3 is a valid element, 24 / 3 = 8
24 % 4 = 0 -> 4 is a valid element, 24 /
4 = 6
24 % 6 = 0 -> 6 is a valid element, 24 / 6 =
4 <- we had this one already!
So, instead of going through 1 to 24, you can stop at 4 which means about 86% gain in speed(!). Ofcourse this is a little less since you have to calculate the other factors(6, 8, 12, 24) as well which can be done by dividing the input with x where x = (input - x * n = 0) & (x < sqrt(input)) | (x E N).
As you might suspect, this especially comes in handy when factorizing large numbers since the time saved in percentage is about (100 - 100 / sqrt(input)). When we take input as infinitely large wel'll notice a 100% decrease in numbers to be calculated. Unfortunately at infinity you'll still have to calculate sqrt(infity) numbers which is an infinite amount :P.
Maybe interesting, even the fastest factorial algorithm delivers tons and tons of overhead. Computing the factorials of the product of two 512 bit primes takes more than 5 years on a distributed network! This characteristic behaviour is cleverly used in the RSA public/private key encryption system which makes it one of the safest encryption systems of the last 25 years.
Either way, here is some javacode on how to do it :P.
...
int input = 24;
int sqrt = (int)Math.sqrt((double)input); //take the root
for(int i = 0; i <= sqrt; i++) //do the loop
if ((input % i) == 0) //is the input dividable by the number?
System.out.println(i + " / " + input / i); //then print the numbers
...
MADRAGE
