| Age | Commit message (Collapse) | Author |
|---|
|
|
|
|
|
|
|
Our initial implementation of part 2 of week 82 has an exponential
worst case time complexity. By introducing caching and using pointers
instead of copying strings, we now have a quadratic worst case
time complexity (and a quadratic space requirement).
|
|
When hunting for the next prime which divides $gcd, exploit the
fact that, other than 2 and 3, all primes are of the form
6 * k +/-1, for some positive integer k.
|
|
Improved the running time of the algorithm from O (sqrt (gcd ($M, $N)))
to O (sqrt (p) + |f| log |f|) where p is the largest prime factor
of gcd ($M, $N), and |f| is total number of factors.
This is not an improvement if the gcd is a prime, but a dramatic
improvement if the gcd contains lots of prime factors.
|
|
|
|
|
|
|
|
|
|
|
|
|
