Find all the positive divisors of a positive integer

Posted on

Problem

This came from this question.

Find all the positive divisors of an integer >= 2.

Can stop when i * i >= number.

Please review for speed and style.

``````public class IntWithDivisors
{
public override int GetHashCode()
{
return Number;
}
public override bool Equals(object obj)
{
if(obj is IntWithDivisors)
{
return ((IntWithDivisors)obj).Number == this.Number;
}
return false;
}
public override string ToString()
{
return \$"number {Number}    Devisors " + string.Join(", ", Divisors);
}

public List<int> Divisors { get; } = new List<int>();
public int Count { get { return Divisors.Count(); } }
public int Number { get; }
public IntWithDivisors(int number)
{
if (number < 2)
{
throw new ArgumentOutOfRangeException();
}
Number = number;
Divisors = IntDivisors(number);
}
}
public static List<int> IntDivisors(int num)
{
//Debug.WriteLine(\$"nIntDevisors  {num}");
List<int> intDivisors = new List<int>();
int i;
int incr;
if(num / 2 * 2 == num)
{
i = 2;
incr = 1;
}
else
{
i = 3;
incr = 2;
}
for(; i*i < num; i += incr)
{
int numOveri = num / i;
if (numOveri * i == num)
{
//Debug.WriteLine(i);
}
}
if(i*i == num)
{
}
intDivisors.Sort();
return intDivisors;
}
``````

Solution

Why is the implementation of the algorithm a static method outside of the class `IntWithDivisors`? Is it in `class Program`? It shouldn’t be there.

It is unusual to do complex work in the constructor. A constructor should only perform initialization. See answer of Telastyn in how complex a constructor should be. There are different possibilities to solve this

E.g. lazy evaluation:

``````private List<int> _divisors;
public List<int> Divisors
{
get {
if (_divisors == null) {
_divisors = IntDivisors(Number);
}
return _divisors;
}
}
``````

Another option is to simply call a method to get the result.

This leads us to the next question: what is the task of the class `IntWithDivisors`? Do we really need to store the input number together with the output? Do we really need to override `Equals` and `GetHashCode`?

I would rather opt for a minimalist but reusable and flexible approach in the LINQ style as extension method implemented as iterator.

I observed that the starting `i` is one bigger than `incr`. We can use this fact to simplify the initialization.

Testing if a number is even is usually done with the modulo operator which yields the remainder of the division `num % 2 == 0`.

`numOveri` is a strange name. I renamed it to `quotient` and `i` to `divisor`.

The divisors are tested in ascending order; however, the quotients accumulate in descending order. Therefore, we can return the divisors immediately with `yield return` and store the quotients in a list. We then need to reverse this list before we return its items.

``````public static class IntExtensions
{
public static IEnumerable<int> SelectDivisors(this int num)
{
yield return 1;

int incr = num % 2 == 0 ? 1 : 2;
var largeDivisors = new List<int>();
for (int divisor = incr + 1; divisor * divisor <= num; divisor += incr) {
int quotient = num / divisor;
if (quotient * divisor == num) {
yield return divisor;
if (quotient != divisor) {
}
}
}

largeDivisors.Reverse();
for (int k = 0; k < largeDivisors.Count; k++) {
yield return largeDivisors[k];
}

yield return num;
}
}
``````

We can use this extension method like this (shown in a little test routine):

``````int[] numbers = new[] { 9, 12, 15, 16, 17, 27, 54 };
foreach (int num in numbers) {
Console.Write(\$"Number {num} has divisors ");
foreach (int n in num.SelectDivisors()) {
Console.Write(n + " ");
}
Console.WriteLine();
}
``````

What I ended up with

``````public static class IntExtensions
{
public static IEnumerable<int> SelectDivisors(this int num)
{
yield return 1;

int incr = (num / 2 * 2 == num) ? 1 : 2;
var largeDivisors = new List<int>();
for (int smallDivisor = incr + 1; smallDivisor * smallDivisor <= num; smallDivisor += incr)
{
int largeDivisor = num / smallDivisor;
if (largeDivisor * smallDivisor == num)
{
yield return smallDivisor;
if (largeDivisor != smallDivisor)
{