Основной коэффициент 300 000 000 000?

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

64 имеет только один простой множитель, 2. Вы обнаружите это довольно тривиально, если будете продолжать делить 2 до тех пор, пока больше не сможете.

$ time factor 300000000000 > /dev/null

real        0m0.027s
user        0m0.000s
sys         0m0.001s

Вы делаете что-то не так, если на это уходит час. У вас может быть даже где-то бесконечный цикл - убедитесь, что вы не используете 32-битные целые числа.

Ключ к пониманию того, почему квадратный корень важен, заключается в том, что каждый множитель n ниже квадратного корня n имеет соответствующий множитель выше. Чтобы увидеть это, представьте, что если x множитель n, то x / n = m, что означает, что x / m = n, следовательно, m также множитель.

Я бы не ожидал, что это займет очень много времени - это не очень много.

Не могли бы вы привести пример номера, который вызывает трудности с кодом?

Вот один сайт, на котором вы можете получить ответы: Factoris - Онлайн-сервис факторизации. Он может обрабатывать действительно большие числа, но также может факторизовать алгебраические выражения.

Самые быстрые алгоритмы - это ситовые алгоритмы, основанные на тайных областях дискретной математики (по крайней мере, над моей головой), которые сложно реализовать и протестировать.

Самым простым алгоритмом факторинга, вероятно, является (как говорили другие) Решето Эратосфена. Что нужно помнить об использовании этого для множителя числа N:

• Общая идея: вы проверяете возрастающую последовательность возможных целочисленных множителей x, чтобы увидеть, равномерно ли они делят ваш номер кандидата N (в C / Java / Javascript проверяйте, N % x == 0), и в этом случае N не является простым.
• вам просто нужно подняться до sqrt(N), но на самом деле не вычислять sqrt(N): loop, пока ваш тестовый фактор x проходит тест x*x<N
• если у вас есть память, чтобы сохранить кучу предыдущих простых чисел, используйте только их в качестве тестовых факторов (и не сохраняйте их, если простое P не проходит тест P*P > N_max, так как вы никогда не будете использовать их снова
• Даже если вы не сохраните предыдущие простые числа, для возможных множителей x просто отметьте 2 и все нечетные числа. Да, это займет больше времени, но не намного дольше для чисел разумного размера. функция подсчета простых чисел и ее приближения могут сказать вам, какая доля чисел является простой; эта доля уменьшается очень медленно. Даже для 2 ⁶⁴ = приблизительно 1,8x10 ¹⁹ примерно одно из каждых 43 чисел является простым (= одно из каждых 21,5 нечетных чисел является простым). Для множителей чисел меньше 2 ⁶⁴ эти множители x меньше 2 ³², где примерно одно из каждых 20 чисел является простым = одно из каждых 10 нечетных чисел равно основной. Таким образом, вам придется протестировать в 10 раз больше чисел, но цикл должен быть немного быстрее, и вам не придется возиться с хранением всех этих простых чисел.

Есть также несколько более старых и простых алгоритмов сита, которые немного сложнее, но все же довольно понятны. См. Диксон, Shanks ' и Ферма алгоритмы факторинга. Я однажды прочитал статью об одном из них, не могу вспомнить, какой из них, но все они довольно просты и используют алгебраические свойства разностей квадратов.

Если вы просто проверяете, является ли число N простым, и на самом деле не заботитесь о самих факторах, используйте вероятностный тест на простоту. Я думаю, что Миллера-Рабина является наиболее стандартным.

Я потратил на это некоторое время, так как меня это просто затянуло. Я пока не буду вставлять здесь код. Вместо этого, если вам интересно, просмотрите this factor.py gist.

Имейте в виду, я ничего не знал о факторинге (до сих пор не знаю) до того, как прочитал этот вопрос. Это просто Python-реализация ответа BradC, приведенного выше.

На моем MacBook требуется 0,002 секунды, чтобы разложить на множитель число, указанное в вопросе (600851475143).

Очевидно, должны быть гораздо более быстрые способы сделать это. Моей программе требуется 19 секунд для вычисления множителей 6008514751431331. Но Factoris выдаст ответ в кратчайшие сроки.

Конкретный номер 300425737571? Это тривиально превращается в 131 * 151 * 673 * 22567. Я не понимаю, в чем вся суета ...

Вот вам добрые дела от Haskell :)

primeFactors n = factor n primes
  where factor n (p:ps) | p*p > n = [n]
                        | n `mod` p /= 0 = factor n ps
                        | otherwise = p : factor (n `div` p) (p:ps)
        primes = 2 : filter ((==1) . length . primeFactors) [3,5..]

На их поиск потребовалось около 0,5 секунды, так что я бы назвал это успехом.

Вы можете использовать сито Эратосфена, чтобы найти простые числа и посмотреть, делится ли ваше число на эти ты ищешь.

Вам нужно только проверить его остаток по модулю (n), где n - простое число ‹= sqrt (N), где N - число, которое вы пытаетесь разложить на множители. Это действительно не должно занять больше часа, даже на очень медленном компьютере или TI-85.

Ваш алгоритм должен быть FUBAR. На моем нетбуке с тактовой частотой 1,6 ГГц на Python это занимает всего 0,1 с. Python не известен своей молниеносной скоростью. Однако он имеет целые числа произвольной точности ...

import math
import operator

def factor(n):
    """Given the number n, to factor yield a it's prime factors.
    factor(1) yields one result: 1. Negative n is not supported."""
    M = math.sqrt(n)  # no factors larger than M
    p = 2             # candidate factor to test
    while p <= M:     # keep looking until pointless
        d, m = divmod(n, p)
        if m == 0:
            yield p   # p is a prime factor
            n = d     # divide n accordingly
            M = math.sqrt(n)  # and adjust M
        else:
            p += 1    # p didn't pan out, try the next candidate
    yield n  # whatever's left in n is a prime factor

def test_factor(n):
    f = factor(n)
    n2 = reduce(operator.mul, f)
    assert n2 == n

def example():
    n = 600851475143
    f = list(factor(n))
    assert reduce(operator.mul, f) == n
    print n, "=", "*".join(str(p) for p in f)

example()

# output:
# 600851475143 = 71*839*1471*6857

(Этот код, кажется, работает вопреки тому факту, что я недостаточно разбираюсь в теории чисел, чтобы заполнить наперсток.)

Просто чтобы немного расширить / улучшить предложения "только проверять нечетные числа, не заканчивающиеся на 5" ...

Все простые числа больше 3 либо на единицу больше, либо на единицу меньше кратного 6 (6x + 1 или 6x - 1 для целых значений x).

Это не займет так много времени, даже с относительно наивной грубой силой. Для этого конкретного числа я могу мысленно разложить его примерно за одну секунду.

Вы говорите, что не хотите решений (?), Но вот ваш "тонкий" намек. Единственные простые множители числа - это три младших простых числа.

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

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