Brute force
To factorise numbers can be done amazingly fast with a dumb algorithm on a computer. Run over to http://www.cryptographic.co.uk/factjava2.html by Andrew Hodges and see what patterns you discover with your favourite number.
http://www.cryptographic.co.uk/factorise.html gives a bit more background.
I was born in 1952. If you turn it partly upside down and read it from right to left you get 25x61 = 1952.
October 30th, 2009 at 6:38 am
What amazes me is how much faster this is today compared to the BASIC script I wrote to do this 20ish years ago.
My code was essentially this:
Print “Type a number to factor.”
Input X
For n=2 to X/2 (look at all numbers from 2 through 1/2 of X)
If X/n = ABS(X/n) then X = X / n: print “Factor: “;n
next n
End
If I typed “Run Factors” I would get this:
Type a number to factor.
? 856
Factor: 2
Factor: 2
Factor: 2
Factor: 107
That is functionally very similar to this applet I’m sure. The difference is the time it takes. On my Atari 800XL that code would take a few seconds to run — it was not instant.
I love how they’ve taken advantage of the added speed to allow tests on a series of integers.
October 30th, 2009 at 7:59 am
I agree about the drastic improvement in speed. In the old days I would use Eratosthenes’ Sieve to find all primes below a certain limit.
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes