I've written a program that attempts to find Amicable Pairs. This requires finding the sums of the proper divisors of numbers.
Here is my current sumOfDivisors()
method:
int sumOfDivisors(int n)
{
int sum = 1;
int bound = (int) sqrt(n);
for(int i = 2; i <= 1 + bound; i++)
{
if (n % i == 0)
sum = sum + i + n / i;
}
return sum;
}
So I need to do lots of factorization and that is starting to become the real bottleneck in my application. I typed a huge number into MAPLE and it factored it insanely fast.
What is one of the faster factorization algorithms?
The method will work, but will be slow. "How big are your numbers?" determines the method to use: