Простой коэффициент 300 000 000 000?

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

Вот несколько советов, чтобы несколько ускорить его:

• Начинайте низко, а не высоко
• Не утруждайте себя проверкой каждого потенциального фактора, чтобы увидеть, является ли он простым-просто проверьте вероятные простые числа (нечетные числа, которые заканчиваются на 1,3,7 или 9)
Не утруждайте себя проверкой четных чисел (все делится на 2) или коэффициентов, которые заканчиваются на 5 (все делится на 5). Конечно, на самом деле не пропускайте 2 и 5!! Когда вы найдете простой множитель, обязательно разделите его-не продолжайте использовать свое массивное исходное число. Смотрите мой пример ниже.
• Если вы нашли фактор, не забудьте проверить его еще раз, чтобы увидеть, есть ли он там несколько раз. Ваш номер может быть 2x2x3x7x7x7x31 или что-то в этом роде.
• остановитесь, когда достигнете >= sqrt (оставшееся большое число)

Edit: простой пример: Вы находите факторы 275.

1. Тест 275 делимости на 2. Означает ли 275/2 = int (275/2)? № Неудачный.
2. Тест 275 делимости на 3. Неудачный.
3. пропустить 4!
Тест 275 на делимость на 5. Да! 275/5 = 55. Итак, ваш новый тестовый номер теперь 55.
4. Тест 55 для делимости на 5. Да! 55/5 = 11. Итак, ваш новый тестовый номер теперь 11.
5. но 5 > sqrt (11), поэтому 11 является простым, и вы можете остановиться!

Итак 275 = 5 * 5 * 11

Больше смысла?

Факторинг больших чисел-сложная задача. На самом деле так трудно, что мы полагаемся на него, чтобы обеспечить безопасность RSA. Но взгляните на страницу Википедиидля некоторых указателей на алгоритмы, которые могут помочь. Но для такого маленького числа это действительно не должно занимать так много времени, если только вы не повторяете работу снова и снова, что вам не нужно где-то.

Для решения методом перебора помните, что вы можете выполнить некоторые мини-оптимизации:

• Проверьте 2 специально, затем только проверьте нечетное число.
Вам нужно только проверить до квадратного корня из числа (если вы не найдете к тому времени никаких факторов, то число будет простым). Как только вы найдете фактор, не используйте исходное число для поиска следующего фактора, разделите его на найденный фактор и найдите новое меньшее число. Когда вы найдете фактор, разделите его на столько раз, сколько сможете. После этого вам никогда не нужно будет проверять это число или любые другие меньшие числа снова.
• Если вы сделаете все вышеперечисленное, каждый новый фактор, который вы найдете, будет простым, так как все меньшие факторы уже были удалены.

Вот решение XSLT!

Это преобразование XSLT занимает 0,109 секунды .

<xsl:stylesheet version="2.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
 xmlns:xs="http://www.w3.org/2001/XMLSchema"
 xmlns:saxon="http://saxon.sf.net/"
 xmlns:f="http://fxsl.sf.net/"
 exclude-result-prefixes="xs saxon f"
 >
 <xsl:import href="../f/func-Primes.xsl"/>

 <xsl:output method="text"/>


 <xsl:template name="initial" match="/*">
   <xsl:sequence select="f:maxPrimeFactor(600851475143)"/>
 </xsl:template>

 <xsl:function name="f:maxPrimeFactor" as="xs:integer">
   <xsl:param name="pNum" as="xs:integer"/>

   <xsl:sequence select=
    "if(f:isPrime($pNum))
       then $pNum
       else
         for $vEnd in xs:integer(floor(f:sqrt($pNum, 0.1E0))),
             $vDiv1 in (2 to $vEnd)[$pNum mod . = 0][1],
             $vDiv2 in $pNum idiv $vDiv1
           return 
             max((f:maxPrimeFactor($vDiv1),f:maxPrimeFactor($vDiv2)))
    "/>
 </xsl:function>
</xsl:stylesheet>

Это преобразование дает правильный результат (максимальный простой коэффициент 600851475143) всего за 0,109 сек..:

6857

Преобразование использует f:sqrt() и еще f:isPrime() определено в FXSL 2.0 -- библиотека для функционального программирования в XSLT. FXSL сама она написана полностью в XSLT.

f:isPrime() использование маленькая теорема Ферма так что эффективно определить первичность.

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

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

$ time factor 300000000000 > /dev/null

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

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

Ключ к пониманию того, почему важен квадратный корень, заключается в том, что каждый фактор 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): цикл, пока ваш тестовый фактор x проходит тест x*x<N
• Если у вас есть память, чтобы сохранить кучу предыдущих простых чисел, используйте только их в качестве тестовых факторов (и не сохраняйте их, если простое число P не пройдет тест P*P > N_max, так как вы никогда не будете использовать их снова
• Даже если вы не сохраните предыдущие простые числа, для возможных факторов x просто проверьте 2 и все нечетные числа. Да, это займет больше времени, но не так уж много времени для разумных размеров чисел. Функцияподсчета простых чисел и ее приближения могут сказать вам, какая доля чисел является простой; эта доля уменьшаетсяочень медленно. Даже для 2⁶⁴ = приблизительно 1. 8x10¹⁹, примерно одно из каждых 43 чисел является простым (=одно из каждых 21,5 нечетных чисел является простым). Для коэффициентов чисел меньше, чем 2⁶⁴, эти факторы x являются меньше, чем 2³² где примерно одно из каждых 20 чисел является простым = одно из каждых 10 нечетных чисел является простым. Таким образом, вам придется проверить в 10 раз больше чисел, но цикл должен быть немного быстрее, и вам не нужно возиться с хранением всех этих простых чисел.

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

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

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

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

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

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

Конкретное число-300425737571? Это тривиально факторы в 131 * 151 * 673 * 22567. Я не понимаю, из-за чего весь сыр-бор...

Вот вам, ребята, доброта Хаскелла:)

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..]

Взял его с собой .5 секунд, чтобы найти их, так что я бы назвал это успехом.

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

Вам нужно только проверить, что это остаток mod (n), где n-простое число

Ваш алгоритм должен быть FUBAR. Это занимает всего около 0,1 секунды на моем нетбуке с частотой 1,6 ГГц в 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).

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

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

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

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