Мне нужен оптимальный алгоритм, чтобы найти наибольший делитель числа N. Предпочтительно в C ++ или C #

Question

В настоящее время я использую следующий код, но он очень медленный для больших чисел

        static int divisor(int number)
        {
            int i;
            for (i = number / 2; i >= 1; i--)
            {
                if (number % i == 0)
                {
                    break;
                }
            }
            return i;
        }

Answer 1

Сначала подумайте, что вы можете найти наименьший делитель d (конечно, не равный 1), затем N / d будет самым большим делителем, который вы ищете.

Например, если N делится на 3, вам понадобится 2 итерации, чтобы найти ответ - в вашем случае это будет около N / 6 итераций.

Редактировать: Для дальнейшего улучшения вашего алгоритма вы можете перебирать только нечетные числа (после проверки, является ли ваше число четным) или, что еще лучше, если у вас есть предварительно вычисленный список простых чисел, вы можете итерируйте их только потому, что наименьший делитель, очевидно, является простым числом.

Answer 2

Не знаю, является ли это оптимальным решением, но вам, вероятно, лучше начать с 2, чем идти вверх, например:

  static int divisor(int number)
    {
        int i;
        for (i = 2; i <sqrt(number); i++)
        {
            if (number % i == 0)
            {
                break;
            }
        }
        return number/i;
    }

EDIT

, чтобы заставить его работать и с простыми числами:

 static int divisor(int number)
    {
        int i;
        for (i = 2; i <=sqrt(number); i++)
        {
            if (number % i == 0)
            {
                return number/i;
            }
        }
        return 1;
    }

Answer 3

Одним из стандартных отраслевых методов для нахождения факторов больших чисел является алгоритм Quadratic Sieve.

Прочтите это:

http://en.wikipedia.org/wiki/Quadratic_sieve

PS выТакже следует учитывать, насколько велики ваши цифры.Различные алгоритмы факторизации имеют тенденцию работать хорошо для определенного размера, а не для других.Как отмечалось в статье QS вики, этот метод, как правило, самый быстрый для чисел менее 100 знаков после запятой.

Answer 4

Огромная оптимизация (не уверенная в том, что она полностью оптимальна - вам придется спросить у математика), это поиск вверх, используя только простые числа. Как сказали Владимир и Баннит, лучше искать вверх, потому что вы найдете это намного быстрее. Затем верните обратное (number / i). Однако, если вы уже пробовали 2 и выпали без дела, нет смысла пытаться 4 или 6. Аналогично, если вы пробовали 3, нет смысла пытаться 6 или 9.

Так что, если время выполнения является большой проблемой, у вас может быть список первых 100 простых чисел, жестко запрограммированных в вашей программе. Проверьте каждый из них. Если к тому времени вы не найдете ответа, вы можете просто увеличить его на 2 (пропуская четные числа).

Answer 5

Чтобы ограничить пространство поиска, вы должны начать с 2 и работать до квадратного корня из числа. Статистически говоря, гораздо больше чисел (в конечном пространстве поиска), делимых на 2, чем на 27, поэтому вы с большей вероятностью получите низкий делитель, чем высокий.

Вы найдете большую разницу при использовании квадратного корня, а не половину значения при обработке (например) 1 000 000. Разница между областью поиска 500 000 для вашего метода и 1000 для метода квадратного корня является значительной.

Еще одним преимуществом является уменьшение пространства поиска вдвое вперед путем дисконтирования кратных двум. Затем, когда у вас самый низкий делитель, самый высокий делится просто на число, деленное на это.

псевдокод:

if n % 2 == 0:              # Halve search space straight up.
    print n / 2
else:
    i = 3                   # Start at 3.
    while i * i <= n:       # Or use i <= sqrt(n), provided sqrt is calc'ed once
        if n % i  == 0:
            print n / i     # If multiple, get opposite number, print and stop
            break
        i = i + 2           # Only need to process odd numbers

Answer 6

Найдите первое простое число, которое делит число N. Допустим, что простое число равно p.Разделите N на d.Это необходимый результат, который вы хотите.

Answer 7

Оптимизация: нечетное число не может иметь четное число в качестве наибольшего делителя. Используйте этот фильтр на номер рано. Так что если дано нечетное число.

• Сначала делим с 2.

• Затем уменьшаем i на 2 каждый раз в петля

Это улучшит скорость для нечетных чисел.

Answer 8

Лучший алгоритм будет зависеть от того, насколько огромными будут ваши числа.

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

Опять же, в зависимости от вашей шкалы, это может быть даже вариант простого вычисления большого списка простых чисел, его сохранения, а затемс помощью поиска по входному номеру в этом списке для наименьшего делителя, который также сразу же вызовет наибольший делитель.

Answer 9

Некоторые дополнительные оптимизации:

1.  If even then divisable by 2.
2.  If the sum of the digits is divisable by 3, then number is divisble by 3 (ie 78 = 7 + 8 = 15 = 1 + 5 = 6 which is divisable by 3)
3.  If it ends in 0 or 5 it is divisable by 5

Гордон.

Answer 10

Посмотрите здесь: - http://programmingpraxis.com/contents/themes/#Prime%20Numbers

Программирование Praxis регулярно ставит перед людьми задачи по программированию, чтобы они могли немного повеселиться в пятницу в обеденное время.Эта конкретная проблема часто возникает, и есть несколько хорошо известных алгоритмов для ее решения, проиллюстрированных кодом.