Вычисление простых множителей в C#

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

Основные факторы

Простые множители (делители) целочисленного значения - это простые числа, на которые значение можно разделить, не оставляя остатка. Например, простые множители числа пятнадцать равны трем и пяти, так как 3 х 5 = 15, и оба эти множителя являются простыми. Возможно, что один и тот же простой множитель может появиться дважды в списке, например, простые множители для двенадцати, которые равны двум, двум и трем (2 x 2 x 3 = 12). Каждое положительное целое число может быть выражено в виде списка его простых множителей, и каждое положительное целое число имеет один уникальный набор простых множителей.

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

Алгоритм простой факторизации

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

Алгоритм факторизации прямого поиска состоит из следующих шагов. Для этого процесса требуется, чтобы у вас был заранее рассчитанный список доступных простых чисел:

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

Ключевым элементом этого алгоритма является требование к списку простых чисел. Они могут быть рассчитаны с использованием вариации алгоритма Решета Эратосфена. Используемый код будет немного изменен для алгоритма первичной факторизации.

Класс Eratosthenes

Реализация Решета Эратосфена, генерирует список всех простых чисел в заданном диапазоне значений. Для реализации этой статьи мы создадим класс, который выполняет это вычисление. Однако вместо того, чтобы генерировать все простые числа в пределах диапазона, мы будем вычислять новое простое число только тогда, когда оно нам потребуется. Мы также сохраним список ранее вычисленных простых чисел, чтобы их никогда не нужно было пересчитывать.

Для начала создайте новое консольное приложение и добавьте класс с именем "Eratosthenes". Этот класс будет выполнять вычисление простых чисел по требованию. Для эффективной работы он будет содержать набор известных в настоящее время простых чисел и целочисленную переменную, содержащую последнее проверенное число. Поскольку первое простое число равно двум, для упрощения процесса мы добавим два в список и установим последнее проверенное значение равным двум в конструкторе класса.

Чтобы добавить переменные состояния и конструктор, измените класс Eratosthenes следующим образом:

public class Eratosthenes : IEnumerable<int>
{
    private static List<int> _primes = new List<int>();
    private int _lastChecked;
 
    public Eratosthenes()
    {
        _primes.Add(2);
        _lastChecked = 2;
    }
}

Обратите внимание, что класс реализует универсальный интерфейс IEnumerable. Это связано с тем, что мы собираемся создать итератор, который позволит нам перебирать простые числа, как если бы они хранились в коллекции. Добавьте следующую директиву в верхней части файла кода:

using System.Collections;

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

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

private bool IsPrime(int checkValue)
{
    bool isPrime = true;
 
    foreach (int prime in _primes)
    {
        if ((checkValue % prime) == 0 && prime <= Math.Sqrt(checkValue))
        {
            isPrime = false;
            break;
        }
    }
 
    return isPrime;
}

Фактическая генерация простых чисел будет происходить в итераторе класса. При вызове метода GetEnumerator, либо напрямую, либо в результате выполнения цикла foreach, произойдет двухэтапный процесс. Во-первых, каждое из существующих значений в списке простых чисел будет возвращено с помощью команды yield. Как только этот список будет исчерпан, будут вычислены новые простые числа, добавлены в список для дальнейшего использования и возвращены с использованием второго оператора yield. Это будет продолжаться до тех пор, пока не будет достигнуто максимальное целочисленное значение или пока не будут запрошены дополнительные простые числа.

Чтобы добавить функцию итератора, добавьте в класс следующий код:

public IEnumerator<int> GetEnumerator()
{
    foreach (int prime in _primes)
    {
        yield return prime;
    }
 
    while (_lastChecked < int.MaxValue)
    {
        _lastChecked++;
 
        if (IsPrime(_lastChecked))
        {
            _primes.Add(_lastChecked);
            yield return _lastChecked;
        }
    }
}

Чтобы полностью поддерживать интерфейс IEnumerable<int>, мы также должны реализовать не универсальный интерфейс IEnumerable. Для этого требуется добавить один метод в класс Eratosthenes:

IEnumerator IEnumerable.GetEnumerator()
{
    return GetEnumerator();
}

Метод GetPrimeFactors

Теперь, когда у нас есть класс, который генерирует список простых чисел, мы можем использовать его в алгоритме факторизации прямого поиска. Для этого мы создадим простой метод под названием "GetPrimeFactors". Добавьте следующий метод в класс Program проекта консольного приложения. Метод определен как статический, поскольку мы собираемся вызвать его из основного метода. Однако нет никаких причин, по которым это нельзя было бы изменить, чтобы экземпляра для ваших собственных программ.

private static IEnumerable<int> GetPrimeFactors(int value, Eratosthenes eratosthenes)
{
    List<int> factors = new List<int>();
 
    foreach (int prime in eratosthenes)
    {
        while (value % prime == 0)
        {
            value /= prime;
            factors.Add(prime);
        }
 
        if (value == 1)
        {
            break;
        }
    }
 
    return factors;
}

Метод GetPrimeFactors реализует все пять шагов алгоритма в простой функции. Включены два параметра. Первый параметр принимает значение, которое должно быть сведено к списку простых множителей. Второй параметр - это объект Eratosthenes, который будет предоставлять простые числа.

В первой строке метода создается новый список целых чисел. Это будет использоваться для хранения простых коэффициентов по мере их определения.

Вторая строка начинает цикл по списку простых чисел, предоставленных объектом Eratosthenes. Это включает в себя простые числа, которые уже известны, и любые, которые необходимо будет вычислить. Циклу будет разрешено продолжаться до тех пор, пока не будут определены все основные факторы.

Внутри цикла foreach есть цикл while. Этот вторичный цикл проверяет, может ли факторизуемое значение быть точно разделено на текущее простое число. Если это возможно, простое число добавляется в список факторов, и значение делится соответствующим образом. Цикл while будет продолжать добавлять дубликаты одного и того же простого числа в список до тех пор, пока деление без остатка больше не станет возможным.

Оператор if проверяет, завершен ли процесс. Если факторизуемое значение уменьшилось до единицы, цикл foreach завершается и возвращается список простых множителей. Если нет, выполнение продолжается со следующим простым числом из объекта Eratosthenes.

Тестирование алгоритма

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

Eratosthenes eratosthenes = new Eratosthenes();
 
IEnumerable<int> factors = GetPrimeFactors(120, eratosthenes);
 
foreach (int i in factors)
{
    Console.Write("{0} ", i);   // Выведет "2 2 2 3 5"
}

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