Найти делители числа

Question

Практикуюсь на Codewars. Написал метод поиска делителей числа. Он проходитит все тесты, кроме Performance Random Test. Получил System.OutOfMemoryException. Что с этим можно сделать? Заранее, спасибо!

public static int[] Divisors(int n)
{
    int N = 0;
    int[] divisors = new int[n];
    for (int i = 2; i < n; i++)
    {
        if (n % i == 0)
        {
            divisors[i] = i;
            N++;
        }
    }

    int[] ar = new int[N];
    int j = 0;
    for (int i = 0; i < divisors.Length; i++)
    {
        if (divisors[i] != 0)
        {
            ar[j] = divisors[i];
            j++;
        }
        else if (ar.Length == 0)
        {
            return null;
        }
    }
    return ar;
}

Answer 1

List<int> - лучше решение, когда вы не знаете, сколько будет элементов в коллекции.
Число не может делиться на что-то большее, чем половина этого числа (верно?), следовательно перебор уже можно вести только до n / 2
Еще круче, если перебор проводить только до квадратного корня числа, при этом добавляя и делитель и частное, так как от перестановки множителей местами произведение не меняется.

Но я думаю и то что я написал, можно еще улучшить. Это так, наивная реализация:

public static int[] Divisors(int n)
{
    List<int> divisors = new List<int>();
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            divisors.Add(i);
            if (i * i != n)
                divisors.Add(n / i);
        }
    }
    divisors.Sort(); // это для красивого вывода, но можно убрать в пользу производительности
    return divisors.ToArray();
}

Еще можно не делать .ToArray(), а сделать вот так

public static List<int> Divisors(int n)
{
    //...
    return divisors;
}

Но это зависит от того, обязательное у вас условие вернуть именно массив, или просто так получилось.

БЛОГ НА HUSL

Найти делители числа

Ответы (1 шт):