Премьер-фактор 300 000 000 000?

Question

Мне нужно выяснить основные факторы более 300 миллиардов. У меня есть функция, которая добавляет их в список ... очень медленно! Он работает уже около часа, и я думаю, что до него достаточно далеко. Я делаю это совершенно неправильно или это ожидается?

Редактировать: я пытаюсь найти самый большой простой множитель числа 600851475143.

Edit: Результат:

{
    List<Int64> ListOfPrimeFactors = new List<Int64>();
    Int64 Number = 600851475143;
    Int64 DividingNumber = 2;

    while (DividingNumber < Number / DividingNumber)
    {
        if (Number % DividingNumber == 0)
        {
            ListOfPrimeFactors.Add(DividingNumber);
            Number = Number/DividingNumber;
        }
        else
            DividingNumber++;
        }
        ListOfPrimeFactors.Add(Number);
        listBox1.DataSource = ListOfPrimeFactors;
    }
}

Answer 1

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

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

Теперь вы ищете только 150 миллиардов. Каждый раз вокруг вас следует начинать с фактора, который вы только что нашли. Так что, если 2 был фактором, протестируйте 2 снова. Если следующий фактор, который вы обнаружите, равен 3, то нет смысла тестировать снова 2.

И так далее ...

Answer 2

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

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

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

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

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

То есть 275 = 5 * 5 * 11

Есть смысл?

Answer 3

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

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

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

Answer 4

Вот решение 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() использует небольшую теорему Ферма , чтобы эффективно определить первичность.

Answer 5

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

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

Answer 6

$ time factor 300000000000 > /dev/null

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

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

Answer 7

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

Answer 8

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

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

Answer 9

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

Answer 10

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

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

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

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