Нахождение числа делителей большого целого числа с помощью простой/квадратичной факторизации (C#)

Я пытаюсь получить количество делителей 64-битного целого числа (больше 32-битного)

Мой первый метод (для небольших чисел) заключался в том, чтобы разделить число, пока в результате не получится 1, подсчитать количество совпадающих простых чисел и использовать формулу (1 + P1)(1+ P2)..* (1 + Pn) = количество делителей

Например:

24 = 2 * 2 * 2 * 3 = 2^3 * 3^1

==> (3 + 1)*(1 + 1) = 4 * 2 = 8 делителей

        public static long[] GetPrimeFactor(long number)
        {
            bool Found = false;
            long i = 2;
            List<long> Primes = new List<long>();
            while (number > 1)
            {
                if (number % i == 0)
                {
                    number /= i;
                    Primes.Add(i);
                    i = 1;
                }
                i++;
            }
            return Primes.ToArray();
        }

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

Мой вопрос: как я могу реализовать это квадратное сито?


quadratic factorization primes sieve
person Bartemis    schedule 22.03.2015    source источник
comment
Вам нужно написать большую программу, и поэтому ваш вопрос слишком широк.   -  person President James K. Polk    schedule 22.03.2015
comment
Мой вопрос - это псевдокод для квадратичного решета, это не большая программа, не так ли?   -  person Bartemis    schedule 22.03.2015

Ответы (1)


arrow_upward
2
arrow_downward

Квадратное решето — это метод нахождения больших множителей больших чисел; думаю 10^75, а не 2^64. Квадратичное решето сложно даже в простой форме псевдокода и намного сложнее, если вы хотите, чтобы оно было эффективным. Это слишком много для 64-битных целых чисел и будет медленнее, чем другие методы, специализированные для таких небольших чисел.

Если пробное деление слишком медленно для вас, следующим шагом по сложности является метод ро Джона Полларда; для 64-битных целых чисел вы можете попробовать разделить до некоторого небольшого предела, возможно, простые числа меньше тысячи, а затем переключиться на rho. Вот простой псевдокод для поиска единственного множителя n; вызовите его повторно для составных кофакторов, чтобы завершить факторизацию:

function factor(n, c=1)
    if n % 2 == 0 return 2
    h := 1; t := 1
    repeat
        h := (h*h+c) % n
        h := (h*h+c) % n
        t := (t*t+c) % n
        g := gcd(t-h, n)
    while g == 1
    if g is prime return g
    return factor(g, c+1)

Существуют и другие способы факторизации 64-битных целых чисел, но этот поможет вам начать работу и, вероятно, достаточен для большинства целей; вы можете поискать вариант алгоритма ро Ричарда Брента для небольшого ускорения. Если вы хотите узнать больше, я скромно рекомендую эссе Программирование с использованием простых чисел. в моем блоге.

person user448810    schedule 23.03.2015