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

Не самое быстрое, но это работает!

    static bool IsPrime(long num)
    {
        long checkUpTo = (long)Math.Ceiling(Math.Sqrt(num));
        for (long i = 2; i <= checkUpTo; i++)
        {
            if (num % i == 0)
                return false;
        }
        return true;
    }

Я думаю, что было бы хорошо сохранить где-нибудь все возможные начала, меньшие тогда n и просто выполнить итерации через них для нахождения самого большого делителя. Можно получить начала от prime-numbers.org .

, Конечно, я предполагаю, что Ваше число не является слишком большим:)

Это, вероятно, не всегда быстрее, но более оптимистично относительно этого, Вы находите большой главный делитель:

1. N Ваш номер
2. , Если это является главным тогда return(N)
3. , Вычисляют, начала вплоть до Sqrt(N)
4. Проходят начала в порядке убывания (самый большой первый)
   • Если N is divisible by Prime тогда Return(Prime)

Редактирование: На шаге 3 можно использовать Решето Эратосфена или Решето Atkins или независимо от того, что Вам нравится, но отдельно решето не найдет Вас самым большим простым множителем. (Thats, почему я не выбрал бы сообщение SQLMenace's в качестве официального ответа...)

Мне кажется, что шаг № 2 данного алгоритма не будет всем этим эффективным подход. У Вас нет разумного ожидания, что это является главным.

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

1)  Test = 2 
2)  Current = Number to test 
3)  If Current Mod Test = 0 then  
3a)     Current = Current Div Test 
3b)     Largest = Test
3c)     Goto 3. 
4)  Inc(Test) 
5)  If Current < Test goto 4
6)  Return Largest

Эта версия была 90x быстрее, чем Решето.

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

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

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

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

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

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

Простое решение является парой взаимно рекурсивный функции.

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

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, но алгоритм остается таким же.

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

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.
}

Вот лучший алгоритм, который я знаю (в 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) в худшем случае (когда вход является простым числом).

РЕДАКТИРОВАНИЕ:
Ниже 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

Мой ответ основан на триптихе , но значительно улучшается. Он основан на том факте, что за пределами 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;
}

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

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