Алгоритм нахождения наибольшего простого множителя числа

Question

Каков наилучший подход к вычислению наибольшего простого множителя числа?

Я думаю, что наиболее эффективным будет следующее:

1. Найдите наименьшее простое число, которое делит чисто
2. Проверить, является ли результат деления простым
3. Если нет, найдите следующий самый низкий
4. Перейти к 2.

Я основываю это предположение на том, что легче вычислить малые простые факторы. Это правильно? Какие еще подходы я должен рассмотреть?

Редактировать: Теперь я понял, что мой подход бесполезен, если в игре более двух основных факторов, поскольку шаг 2 не выполняется, когда результат является продуктом двух других простых чисел, поэтому необходим рекурсивный алгоритм. *

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

Answer 1

Вот лучший из известных мне алгоритмов (в Python)

def prime_factors(n):
    """Returns all the prime factors of a positive integer"""
    factors = []
    d = 2
    while n > 1:
        while n % d == 0:
            factors.append(d)
            n /= d
        d = d + 1

    return factors


pfs = prime_factors(1000)
largest_prime_factor = max(pfs) # The largest element in the prime factor list

Вышеуказанный метод работает в O(n) в худшем случае (когда вход является простым числом).

EDIT:
Ниже приведена версия O(sqrt(n)), как предлагается в комментарии. Вот код, еще раз.

def prime_factors(n):
    """Returns all the prime factors of a positive integer"""
    factors = []
    d = 2
    while n > 1:
        while n % d == 0:
            factors.append(d)
            n /= d
        d = d + 1
        if d*d > n:
            if n > 1: factors.append(n)
            break
    return factors


pfs = prime_factors(1000)
largest_prime_factor = max(pfs) # The largest element in the prime factor list

Answer 2

На самом деле есть несколько более эффективных способов найти факторы больших чисел (для более мелких пробное деление работает достаточно хорошо).

Один метод, который очень быстр, если входное число имеет два фактора, очень близких к его квадратному корню, известен как Факторизация Ферма . Он использует тождество N = (a + b) (a - b) = a ^ 2 - b ^ 2 и прост для понимания и реализации. К сожалению, это не очень быстро в целом.

Самым известным методом для вычисления чисел длиной до 100 цифр является Квадратное сито . В качестве бонуса, часть алгоритма легко выполняется с параллельной обработкой.

Еще один алгоритм, о котором я слышал, это Алгоритм Полларда Rho . Он не так эффективен, как Quadratic Sieve в целом, но, кажется, его легче реализовать.

---

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

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

Answer 3

Мой ответ основан на Триптих , но значительно улучшается. Он основан на том факте, что за пределами 2 и 3 все простые числа имеют вид 6n-1 или 6n + 1.

var largestPrimeFactor;
if(n mod 2 == 0)
{
    largestPrimeFactor = 2;
    n = n / 2 while(n mod 2 == 0);
}
if(n mod 3 == 0)
{
    largestPrimeFactor = 3;
    n = n / 3 while(n mod 3 == 0);
}

multOfSix = 6;
while(multOfSix - 1 <= n)
{
    if(n mod (multOfSix - 1) == 0)
    {
        largestPrimeFactor = multOfSix - 1;
        n = n / largestPrimeFactor while(n mod largestPrimeFactor == 0);
    }

    if(n mod (multOfSix + 1) == 0)
    {
        largestPrimeFactor = multOfSix + 1;
        n = n / largestPrimeFactor while(n mod largestPrimeFactor == 0);
    }
    multOfSix += 6;
}

Я недавно написал статью в блоге , объясняющую, как работает этот алгоритм.

Я бы рискнул, что метод, в котором нет необходимости в тесте на первичность (и нет конструкции сита), будет работать быстрее, чем тот, который использует их. Если это так, то это, вероятно, самый быстрый алгоритм здесь.

Answer 4

код JavaScript:

'option strict';

function largestPrimeFactor(val, divisor = 2) { 
    let square = (val) => Math.pow(val, 2);

    while ((val % divisor) != 0 && square(divisor) <= val) {
        divisor++;
    }

    return square(divisor) <= val
        ? largestPrimeFactor(val / divisor, divisor)
        : val;
}

Пример использования:

let result = largestPrimeFactor(600851475143);

Вот пример кода :

Answer 5

    //this method skips unnecessary trial divisions and makes 
    //trial division more feasible for finding large primes

    public static void main(String[] args) 
    {
        long n= 1000000000039L; //this is a large prime number 
        long i = 2L;
        int test = 0;

        while (n > 1)
        {
            while (n % i == 0)
            {
                n /= i;     
            }

            i++;

            if(i*i > n && n > 1) 
            {
                System.out.println(n); //prints n if it's prime
                test = 1;
                break;
            }
        }

        if (test == 0)  
            System.out.println(i-1); //prints n if it's the largest prime factor
    }

Answer 6

Все числа могут быть выражены как произведение простых чисел, например:

102 = 2 x 3 x 17
712 = 2 x 2 x 2 x 89

Вы можете найти их, просто начав с 2 и просто продолжая делить, пока результат не станет кратным вашему числу:

712 / 2 = 356 .. 356 / 2 = 178 .. 178 / 2 = 89 .. 89 / 89 = 1

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

number = 712;
currNum = number;    // the value we'll actually be working with
for (currFactor in 2 .. number) {
    while (currNum % currFactor == 0) {
        // keep on dividing by this number until we can divide no more!
        currNum = currNum / currFactor     // reduce the currNum
    }
    if (currNum == 1) return currFactor;    // once it hits 1, we're done.
}

Answer 7

Самое простое решение - это пара взаимно рекурсивных функций.

Первая функция генерирует все простые числа:

1. Начните со списка всех натуральных чисел больше 1.
2. Удалить все числа, которые не являются простыми. То есть числа, которые не имеют главных факторов (кроме самих себя). Смотри ниже.

Вторая функция возвращает простые множители заданного числа n в порядке возрастания.

1. Возьмите список всех простых чисел (см. Выше).
2. Удалить все числа, которые не являются коэффициентами n.

Наибольший простой множитель n - это последнее число, заданное второй функцией.

Для этого алгоритма требуется ленивый список или язык (или структура данных) с семантикой по требованию .

Для пояснения, вот одна (неэффективная) реализация вышеперечисленного в Haskell:

import Control.Monad

-- All the primes
primes = 2 : filter (ap (<=) (head . primeFactors)) [3,5..]

-- Gives the prime factors of its argument
primeFactors = factor primes
  where factor [] n = []
        factor xs@(p:ps) n =
          if p*p > n then [n]
          else let (d,r) = divMod n p in
            if r == 0 then p : factor xs d
            else factor ps n

-- Gives the largest prime factor of its argument
largestFactor = last . primeFactors

Чтобы сделать это быстрее, нужно просто умнее определять, какие числа являются простыми и / или множителями n, но алгоритм остается тем же.

Answer 8

Похоже на ответ @Triptych, но также отличается. В этом примере список или словарь не используется. Код написан на Ruby

def largest_prime_factor(number)
  i = 2
  while number > 1
    if number % i == 0
      number /= i;
      i -= 1
    end
    i += 1
  end
  return i
end

largest_prime_factor(600851475143)
# => 6857

Answer 9

n = abs(number);
result = 1;
if (n mod 2 == 0) {
  result = 2;
  while (n mod 2 = 0) n /= 2;
}
for(i=3; i<sqrt(n); i+=2) {
  if (n mod i == 0) {
    result = i;
    while (n mod i = 0)  n /= i;
  }
}
return max(n,result)

Существуют некоторые тесты по модулю, которые являются излишними, поскольку n никогда нельзя разделить на 6, если все факторы 2 и 3 были удалены Вы можете разрешить только простые числа для i, что показано здесь в нескольких других ответах.

Вы могли бы на самом деле переплетать сито Эратосфена здесь:

• Сначала создайте список целых чисел вверх до sqrt (n).
• В цикле for отметьте все кратные я до нового sqrt (n) как не премьер и используйте вместо этого цикл while.
• установить i на следующее простое число в список.

Также см. этот вопрос .

Answer 10

Я знаю, что это не быстрое решение. Размещение, как мы надеемся, облегчает понимание медленного решения.

 public static long largestPrimeFactor(long n) {

        // largest composite factor must be smaller than sqrt
        long sqrt = (long)Math.ceil(Math.sqrt((double)n));

        long largest = -1;

        for(long i = 2; i <= sqrt; i++) {
            if(n % i == 0) {
                long test = largestPrimeFactor(n/i);
                if(test > largest) {
                    largest = test;
                }
            }
        }

        if(largest != -1) {
            return largest;
        }

        // number is prime
        return n;
    }