Премьер-фактор 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

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

Простейшим алгоритмом факторинга, вероятно, (как уже говорили другие) является сито Эратосфена. Что нужно помнить, чтобы использовать это для вычисления числа 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 простым, и на самом деле вас не волнуют сами факторы, используйте вероятностный критерий простоты . Миллер-Рабин самый стандартный, я думаю.

Answer 2

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

Answer 3

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

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 секунд, чтобы найти их, поэтому я бы назвал это успехом.

Answer 4

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

Answer 5

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

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

Answer 6

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

Answer 7

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

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

Answer 8

Ваш алгоритм должен быть 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

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

Answer 9

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

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