0

Практикуюсь на 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;
}
5
  • а что должен делать второй цикл тут?
    – Grundy
    9 фев 2021 в 11:44
  • покажите код как у Вас проходит рандом тест 9 фев 2021 в 11:46
  • new int[n]; нет смысла в выделении сразу такого большого массива. В большинстве случаев количество делителей у числа намного меньше чем само значение числа.
    – Grundy
    9 фев 2021 в 11:47
  • наверное самое простое решение - использовать List<int> вместо массива. Это позволит уйти от второго цикла и от выделения огромного куска памяти одномоментно
    – Grundy
    9 фев 2021 в 11:48
  • Самая базовая оптимизация, рассмативать делители не до n, а до n / 2, а ещё лучше до квадратного корня из n. Ну и как вам написали, нет смысла хранить огромное количество нулей в первом массиве
    – SmorcIRL
    9 фев 2021 в 11:56

1 ответ 1

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

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

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;
}

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

5
  • откуда эти n/2 взялись? Уже не первый раз попадаются. Достаточно проверять до квадратного корня, так как после него уже пары для делителей, которые уже были. Например для числа 100 нет смысла в проверке всех чисел до 50, достаточно проверить все числа до 10 (включительно)
    – Grundy
    9 фев 2021 в 12:17
  • 1
    @Grundy ты точно не путаешь с простыми числами? Потому что 100 еще и на 50 делится. Как мне в список делителей вывести 50, если я только до 10 проверил?
    – aepot
    9 фев 2021 в 12:59
  • 1
    @aepot, если ты разделишь 100 на 2, получишь число 50, нет смысла проверять делится ли 100 на 50 чтобы получить 2
    – Grundy
    9 фев 2021 в 13:00
  • @Grundy обновил ответ.
    – aepot
    9 фев 2021 в 13:06
  • 1
    +1, этот цикл красивее записать с условием i*i <= n так можно не думать об округлении. 10 фев 2021 в 3:24

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.