Now I'm convinced I got lucky and maybe I'm mis-remembering the square root thing.
Take 16 for example... you can't look for all the primes from 1-16 by looking only up to 4!
I'm going to copy the program over to my Win7 machine and run it without the square root trick. My netbook gets super toasty after chugging away for more than a few minutes.
Let's elaborate on the significance of the square root...
ReplyDelete1)
Say you have two positive numbers, 'a' and 'b'. Their product is 'c'. When 'a' and 'b' are equal, they are called 'square roots' of 'c'.
a*b == c
a^2 == b^2 == c
a == b == sqrt(c)
2)
Now, let's assume 'a' and 'b' are not equal. Choose a value for 'a' that is less than 'sqrt(c)'. What can you say about 'b'?
b == c/a
We know that 'b' must be greater than 'sqrt(c)' because:
'c' is constant
'a' is less than sqrt(c)
=> 'b' must increase for any decrease in 'a'.
--
So how does this help you with Euler#3?
Let's define 'a', 'b', and 'c' again, this time with the following properties:
'a' and 'b' are positive integers
a*b == c
a <= sqrt(c)
b >= sqrt(c)
'a' is prime
What must 'a' be if 'c' is prime?
What must 'b' be if 'c' is prime?
As 'a' increases, what must 'b' do?
We know 'a' is prime by our requirements above.
Can we say anything interesting about 'b'?
If 'b' is not prime, what can we say about the prime factors of 'b'?
How do the prime factors of 'b' relate to the prime factors of 'c'?
What can be said about the largest prime factor of 'b' and the largest prime factor of 'c'?
Answering these questions might give you some insight into a recursive algorithm for finding the largest prime factor of 'c'.