Finding Divisors
A divisor (D) of a number (N) is an integer that divides another integer with no remainder. In other words N mod D = 0.
Sometimes, we are interested in finding all divisors of a number. If we are considering a programming solution to this problem, chances are we are dealing with very large numbers or very large collections of numbers. In either case, we want to use an algorithm that is correct and efficient.
An appropriate instinctual approach in C# would look something like this:
static List GetDivisors(int number)
{
var divisors = new List();
for(int i = 2; i < number; ++i)
{
if(number % i == 0)
{
divisors.Add(i);
}
}
return divisors;
}
If you read my post on Prime Number Testing, you’ll know that Int32.Max_Value is prime. To test the efficiency of GetDivisors, I am going to use Int32.Max_Value since it is big and at least has one even divisor. I will use the following console app to test the GetDivisors method:
static void Main(string[] args)
{
var stopwatch = new Stopwatch();
stopwatch.Start();
int number = int.MaxValue - 1;
var divisors = GetDivisors(number);
stopwatch.Stop();
Console.WriteLine("Time Elapsed: " + stopwatch.Elapsed);
Console.Write( number.ToString() + " has " + divisors.Count.ToString() + " divisors.");
Console.ReadLine();
}
Time Elapsed: 00:00:10.0889733
2147483646 has 190 divisors.
10 seconds hurts. If we were using Int64.Max_Value – 1, it would take several thousand years to complete this computing. This blog will look at numbers that exceed Int64.Max_Value, so we are going to need to tune this method.
We know from Prime Number Testing that the greatest possible divisor (GPD) of a number cannot exceed that number divided by its least possible divisor (LPD). Armed with this information, we can change the algorithm, so that GetDivisors() does not check numbers greater than the GPD.
static List GetDivisors(int number)
{
var divisors = new List();
int GPD = number;
bool foundGPD = false;
for(int i = 2; i <= GPD; ++i)
{
if(number % i == 0)
{
divisors.Add(i);
if (!foundGPD)
{
GPD = number / i;
foundGPD = true;
}
}
}
return divisors;
}
We’ll start by setting the GPD = N / 1. We’ll add a false condition that the GPD has been identified. When we find the first divisor, we’ll set the GPD.
Time Elapsed: 00:00:05.1988065
2147483646 has 190 divisors.
This is an improvement, but we can still do better. Whenever we find a divisor, we’ve also identified another divisor. In the case of discovering an LPD, we’ve also found a GPD.
For example, the number here are the divisors for 20 written in ascending order: {2, 4, 5, 10}. Since we know 20 mod 2 = 0 then we also know that 20 mod 10 = 0 (ie 20 mod (20 /2) = 0)! Visually we can see that each pair of divisors is the same number of elements from the middle of the set. So we can improve our algorithm to add 2 divisors for every 1 divisor found. Further, for each divisor found, we can decrease the maximum number to check in our for loop.
static List GetDivisors(int number)
{
var divisors = new List();
int newMax = number;
for (int i = 2; i < newMax; ++i)
{
if (number % i == 0)
{
divisors.Add(i);
divisors.Add(number / i);
newMax = number / i;
}
}
return divisors;
}
Time Elapsed: 00:00:00.0006397
2147483646 has 190 divisors.
We’ve improved the efficiency of the algorithm for Int32 – 1 from over 5s to less than 1ms. But wait, we missed something. What happens if we run the number 36 through GetDivisors()?
Time Elapsed: 00:00:00.0003113
36 has 8 divisors.
Let’s check this out. The divisors of 36 are (2, 3, 4, 6, 9, 12, 18). That’s only 7, so what gives? 36 is a perfect square, so when we add it i = 6, we’re also adding number / i = 6. Adding a quick check on this condition will fix us up.
static List GetDivisors(int number)
{
var divisors = new List();
int newMax = number;
for (int i = 2; i < newMax; ++i)
{
if (number % i == 0)
{
int divisor2 = number / i;
divisors.Add(i);
if(divisor2 != i)
{
divisors.Add(number / i);
}
newMax = number / i;
}
}
return divisors;
}
Time Elapsed: 00:00:00.0003326
36 has 7 divisors.
Prime Factorization
The prime factorization of a positive integer is defined as a list of the integer’s prime factors, together with their multiplicities.
Some examples of prime factorization are:
20 = 2² * 5
27 = 3³
88 = 2³ * 11
156 = 2² * 3 * 13
A trivial example of prime factorization is a prime, which is equal to itself.
We can use the GetDivisors method as a starting point for GetPrimeFactors, however GetPrimeFactors will need to account for multiplicities – ie For a prime factor p of N, the multiplicity of p is the largest exponent a for which p&supa; divides N exactly. The multiplicity of a number will be greater than one when the number has a divisor that is a perfect square. For example 4 is a divisor of 20 and 2² is a member of its prime factorization.
Before we write a method for GetPrimeFactors, lets look at a common approach done by hand. We’ll look for the prime factors of 20 and we’ll start with the lowest prime, 2.
20 mod 2 = 0 ✓
20 / 2 = 1010 mod 2 = 0 ✓
10 / 2 = 55 mod 2 = 1 x
5 mod 3 = 2 x
5 mod 5 = 0 ✓
5 / 5 = 1
The trick is to keep checking if a prime evenly divides our number. If the number divides without a remainder, record the result, then check again that it can be divided by the prime. Unsurprisingly the three modulo checks that result in 0 are the prime factors of 20. Also take note that we don’t actually need to know if a number is prime or not to use this approach. As long as we start with 2 and we exhaust the modulo checks for each number, non-prime numbers will not divide without remainder since their prime factors were exhausted in earlier tries.
The trick to this algorithm is using a while loop. While the number is divisible by p, we’ll add p to the PrimeFactors list and we’ll divide our number by p. As more ps are found the number gets smaller and as a result the for loop gets smaller.
static List GetPrimeFactors(int number)
{
var primeFactors = new List();
for (int p = 2; p < number; ++p)
{
while (number % p == 0)
{
primeFactors.Add(p);
number = number / p;
}
}
return primeFactors;
}
A test of the int.Max_Value – 1 yields a result in less than 1 ms.
Time Elapsed: 00:00:00.0002345
P(2147483646) = {2, 3, 3, 7, 11, 31, 151, 331}