Взгляните сюда: - http://programmingpraxis.com/contents/themes/#Prime%20Numbers

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

Вы в основном столкнулись с проблемой «факторизации больших чисел», которая является основой современного шифрования открытого ключа и известна (или надеется) в вычислительном отношении сложная проблема. Я действительно надеюсь, что вы не найдете намного лучшего решения, иначе вся мировая инфраструктура безопасности рухнет ... :)

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

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

ИЗМЕНИТЬ

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

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

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

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

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

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

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

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

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

• Сначала делите на 2.

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

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

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

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

Гордон.

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

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

В хороших книгах по криптографии, алгоритмике и вычислительной теории чисел вы, вероятно, найдете несколько (возможно, разных) ответов на ваш вопрос.

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

Чтобы ограничить область поиска, вы должны начать с 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