Вопрос:

Как оптимизировать этот код C #?

c# arrays primes object-reference

106 просмотра

1 ответ

3 Репутация автора

У меня есть проблема на платформе программирования (CodeWars - «Найти делители»), и мой алгоритм кажется слишком медленным. Это ошибка, которую я получаю от платформы: процесс был прерван. Это заняло больше 12000 мс

Это инструкция для вызова: Создайте функцию с именем divisors / Divisors, которая принимает целое число и возвращает массив со всеми делителями целого числа (кроме 1 и самого числа). Если число простое, верните строку '(целое число) простое' (ноль в C #)

public static int[] Divisors(int n /* out int numfactors*/)
{
    List<int> divArray = new List<int>(); 
    int div;

    if (isPrime(n))
    {
        return divArray.ToArray();
    }
    else
    {

        for (div = 2; div < n / 2 + 1; div++)
        {
            if (n % div == 0)
            {
                divArray.Add(div);
            }

            return divArray.ToArray();
        }
    }
}

public static bool isPrime(int n)
{
    int d = 2;

    if (n == 1 && n % 2 == 0 && n != 2) return false;

    while (d * d <= n)
    {
        if (n % d == 0) return false;

        d = d + 1;
    }

    return true;
}

Что я делаю не так, как я мог оптимизировать этот алгоритм? Если я проверю простое число, мой код вернет «ничего», я думаю, что это еще одна проблема. если число простое, и я пытаюсь вернуть ноль, моя программа вылетает с: «Ссылка на объект не установлена ​​на экземпляр объекта»

Автор: Andrei Gandi Источник Размещён: 08.11.2017 10:35

Ответы (1)


0 плюса

3293 Репутация автора

Решение

В комментариях к вашему вопросу другие отметили, что в вашей программе есть проблемы с корректностью, которые вам нужно решить, прежде чем беспокоиться о производительности, и это абсолютно верно. Тем не менее, поскольку вы спрашивали о производительности, учтите, что whileцикл IsPrimeи forцикл в Divisorsосновном выполняют одно и то же: перебирая набор потенциальных факторов и определяя, делятся ли они равномерно n. Так:

  1. Почему ты делаешь это дважды? Так как вам нужно составить полный список факторов в случае составного n, почему бы просто не составить весь список заранее, а затем сделать вывод, nпростое ли число из размера списка?

  2. Что еще более важно, почему forцикл Divisorsиспользуется в n/2+1качестве своей верхней границы, когда ваш whileцикл IsPrimeправильно замечает, что вам действительно нужно подняться √n? Да, составной nбудет иметь факторы, которые больше, чем √n, но вам не нужно итерировать выше этой точки, чтобы найти их, потому что для любого, kкоторый делится равномерно n, вы знаете, что n/kтакже делит равномерно n.

Автор: Joe Farrell Размещён: 08.11.2017 11:27
Вопросы из категории :
32x32