Алгоритм для поиска факторов заданного числа. Самый короткий метод?

Ответ 1

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

Ну, это другое. Пусть n - заданное число.

Если n = p1^e1 * p2^e2 * ... * pk^ek, где каждое p - простое число, то число факторов n равно (e1 + 1)*(e2 + 1)* ... *(ek + 1). Подробнее об этом здесь.

Поэтому достаточно найти мощности, при которых появляется каждый простой множитель. Например:

read given number in n
initial_n = n
num_factors = 1;
for (i = 2; i * i <= initial_n; ++i) // for each number i up until the square root of the given number
{
    power = 0; // suppose the power i appears at is 0
    while (n % i == 0) // while we can divide n by i
    {
        n = n / i // divide it, thus ensuring we'll only check prime factors
        ++power // increase the power i appears at
    }
    num_factors = num_factors * (power + 1) // apply the formula
}

if (n > 1) // will happen for example for 14 = 2 * 7
{
    num_factors = num_factors * 2 // n is prime, and its power can only be 1, so multiply the number of factors by 2
}

Например, возьмите 18. 18 = 2^1 * 3*2 => number of factors = (1 + 1)*(2 + 1) = 6. Действительно, коэффициенты 6 18 равны 1, 2, 3, 6, 9, 18.

Вот небольшой контрольный показатель между моим методом и методом, описанным и опубликованным @Maciej. У него есть преимущество в том, что его проще реализовать, в то время как у меня есть преимущество быть быстрее, если изменить только перебирать простые числа, как я сделал для этого теста:

 class Program
{
    static private List<int> primes = new List<int>();

    private static void Sieve()
    {
        bool[] ok = new bool[2000];

        for (int i = 2; i < 2000; ++i) // primes up to 2000 (only need up to sqrt of 1 000 000 actually)
        {
            if (!ok[i])
            {
                primes.Add(i);

                for (int j = i; j < 2000; j += i)
                    ok[j] = true;
            }
        }
    }

    private static int IVlad(int n)
    {
        int initial_n = n;
        int factors = 1;

        for (int i = 0; primes[i] * primes[i] <= n; ++i)
        {
            int power = 0;
            while (initial_n % primes[i] == 0)
            {
                initial_n /= primes[i];
                ++power;
            }
            factors *= power + 1;
        }

        if (initial_n > 1)
        {
            factors *= 2;
        }

        return factors;
    }

    private static int Maciej(int n)
    {
        int factors = 1;
        int i = 2;
        for (; i * i < n; ++i)
        {
            if (n % i == 0)
            {
                ++factors;
            }
        }

        factors *= 2;

        if (i * i == n)
        {
            ++factors;
        }

        return factors;
    }

    static void Main()
    {
        Sieve();


        Console.WriteLine("Testing equivalence...");

        for (int i = 2; i < 1000000; ++i)
        {
            if (Maciej(i) != IVlad(i))
            {
                Console.WriteLine("Failed!");
                Environment.Exit(1);
            }
        }

        Console.WriteLine("Equivalence confirmed!");

        Console.WriteLine("Timing IVlad...");
        Stopwatch t = new Stopwatch();

        t.Start();
        for (int i = 2; i < 1000000; ++i)
        {
            IVlad(i);
        }

        Console.WriteLine("Total milliseconds: {0}", t.ElapsedMilliseconds);
        Console.WriteLine("Timing Maciej...");

        t.Reset();
        t.Start();
        for (int i = 2; i < 1000000; ++i)
        {
            Maciej(i);
        }


        Console.WriteLine("Total milliseconds: {0}", t.ElapsedMilliseconds);
    }
}

Результаты на моей машине:

Тестирование эквивалентности...
Эквивалентность подтверждена!
Сроки IVlad...
Всего миллисекунд: 2448
Сроки Maciej...
Всего миллисекунд: 3951
Нажмите любую клавишу для продолжения.,

Ответ 2

Существует большое количество доступных алгоритмов - от простого пробного детектора до очень сложных алгоритмов для больших чисел. Посмотрите Integer Factorization в Википедию и выберите тот, который вам подходит.

Вот короткая, но неэффективная реализация С#, которая находит количество простых факторов. Если вам нужно количество факторов (не простых факторов), вы должны сохранить основные коэффициенты с их кратностью и вычислить количество факторов впоследствии.

var number = 3 * 3 * 5 * 7 * 11 * 11;

var numberFactors = 0;
var currentFactor = 2;

while (number > 1)
{
    if (number % currentFactor == 0)
    {
        number /= currentFactor;
        numberFactors++;
    }
    else
    {
        currentFactor++;
    }
}

Ответ 3

Вы можете взглянуть на этот алгоритм.

Ответ 4

Вот плод моего короткого обсуждения с |/| ad:)

read given number in n
int divisorsCount = 1;
int i;
for(i = 2; i * i < n; ++i)
{
    if(n % i == 0)
    {
        ++divisorsCount;
    }
}
divisorsCount *= 2;
if(i * i == n)
{
    ++divisorsCount;
}

Ответ 5

Осторожно, этот ответ не является полезным/быстрым для одного значения n.

Метод 1:

Вы можете получить его в O (polylog (n)), если вы поддерживаете справочную таблицу (для первого простого коэффициента числа).

Если gcd (a, b) == 1, то нет. факторов a * b = (нет множителей a) * (нет множителей b)

Следовательно, для заданного числа a * b, если gcd (a, b)!= 1, то мы можем иметь два других числа p и q, где p = a и q = b/gcd (a, b). Таким образом, gcd (p, q) == 1. Теперь мы можем рекурсивно найти число факторов для p и q.

Требуется лишь небольшое количество усилий, чтобы гарантировать, что ни p, ни q не равны 1.

P.S. Этот метод также полезен, когда вам нужно знать количество факторов всех чисел от 1 до n. Это будет порядок O (nlogn + O (справочная таблица)).

Метод 2: (У меня нет прав для этого.)

Если у вас есть поиск первого первичного фактора до n, тогда вы можете узнать все основные факторы в O (logn) и, следовательно, найти количество факторов из них.

P.S. Google "Факторизация в журнале" для лучшего объяснения.

Ответ 6

Должен быть достаточен алгоритм Евклида.