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

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

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

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

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

Еще один алгоритм, о котором я слышал, - это алгоритм Ро Полларда . Это не так эффективно, как квадратичное сито в целом, но кажется, что его легче реализовать.

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

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

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

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

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

Код 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);

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

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

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

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

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

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

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

Этот алгоритм требует наличия ленивого списка или языка (или структуры данных) с семантикой call-by-need .

Для уточнения приведем одну (неэффективную) реализацию вышесказанного в 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.
}

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

Похоже на ответ @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

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

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

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 отметьте все кратные числа от i до Нового sqrt (n) как не prime, и используйте вместо этого цикл while.
• я до следующего простого числа в список.

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

Python итерационный подход путем удаления всех простых множителей из числа

def primef(n):
    if n <= 3:
        return n
    if n % 2 == 0:
        return primef(n/2)
    elif n % 3 ==0:
        return primef(n/3)
    else:
        for i in range(5, int((n)**0.5) + 1, 6):
            #print i
            if n % i == 0:
                return primef(n/i)
            if n % (i + 2) == 0:
                return primef(n/(i+2))
    return n

Я использую алгоритм, который продолжает делить число на его текущий простой коэффициент.

Мое решение в python 3 :

def PrimeFactor(n):
    m = n
    while n%2==0:
        n = n//2
    if n == 1:         # check if only 2 is largest Prime Factor 
        return 2
    i = 3
    sqrt = int(m**(0.5))  # loop till square root of number
    last = 0              # to store last prime Factor i.e. Largest Prime Factor
    while i <= sqrt :
        while n%i == 0:
            n = n//i       # reduce the number by dividing it by it's Prime Factor
            last = i
        i+=2
    if n> last:            # the remaining number(n) is also Factor of number 
        return n
    else:
        return last
print(PrimeFactor(int(input()))) 

Вход: 10 Выход: 5

Вход: 600851475143 Выход: 6857

Вот моя попытка в c#. последняя распечатка - это самый большой простой множитель числа. Я проверил, и это работает.

namespace Problem_Prime
{
  class Program
  {
    static void Main(string[] args)
    {
      /*
       The prime factors of 13195 are 5, 7, 13 and 29.

      What is the largest prime factor of the number 600851475143 ?
       */
      long x = 600851475143;
      long y = 2;
      while (y < x)
      {
        if (x % y == 0)
        {
          // y is a factor of x, but is it prime
          if (IsPrime(y))
          {
            Console.WriteLine(y);
          }
          x /= y;
        }

        y++;

      }
      Console.WriteLine(y);
      Console.ReadLine();
    }
    static bool IsPrime(long number)
    {
      //check for evenness
      if (number % 2 == 0)
      {
        if (number == 2)
        {
          return true;
        }
        return false;
      }
      //don't need to check past the square root
      long max = (long)Math.Sqrt(number);
      for (int i = 3; i <= max; i += 2)
      {
        if ((number % i) == 0)
        {
          return false;
        }
      }
      return true;
    }

  }
}

#python implementation
import math
n = 600851475143
i = 2
factors=set([])
while i<math.sqrt(n):
   while n%i==0:
       n=n/i
       factors.add(i)
   i+=1
factors.add(n)
largest=max(factors)
print factors
print largest

Вычисляет наибольший простой множитель числа с помощью рекурсии в C++. Работа кода объясняется ниже:

int getLargestPrime(int number) {
    int factor = number; // assumes that the largest prime factor is the number itself
    for (int i = 2; (i*i) <= number; i++) { // iterates to the square root of the number till it finds the first(smallest) factor
        if (number % i == 0) { // checks if the current number(i) is a factor
            factor = max(i, number / i); // stores the larger number among the factors
            break; // breaks the loop on when a factor is found
        }
    }
    if (factor == number) // base case of recursion
        return number;
    return getLargestPrime(factor); // recursively calls itself
}

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

Код (Haskell):

f max' x i | i > x = max'
           | x `rem` i == 0 = f i (x `div` i) i  -- Divide x by its factor
           | otherwise = f max' x (i + 1)  -- Check for the next possible factor

g x = f 2 x 2

Следующий алгоритм C++ не самый лучший, но он работает для чисел меньше миллиарда и довольно быстро

#include <iostream>
using namespace std;

// ------ is_prime ------
// Determines if the integer accepted is prime or not
bool is_prime(int n){
    int i,count=0;
    if(n==1 || n==2)
      return true;
    if(n%2==0)
      return false;
    for(i=1;i<=n;i++){
    if(n%i==0)
        count++;
    }
    if(count==2)
      return true;
    else
      return false;
 }
 // ------ nextPrime -------
 // Finds and returns the next prime number
 int nextPrime(int prime){
     bool a = false;
     while (a == false){
         prime++;
         if (is_prime(prime))
            a = true;
     }
  return prime;
 }
 // ----- M A I N ------
 int main(){

      int value = 13195;
      int prime = 2;
      bool done = false;

      while (done == false){
          if (value%prime == 0){
             value = value/prime;
             if (is_prime(value)){
                 done = true;
             }
          } else {
             prime = nextPrime(prime);
          }
      }
        cout << "Largest prime factor: " << value << endl;
 }

Нашел это решение в интернете по "James Wang"

public static int getLargestPrime( int number) {

    if (number <= 1) return -1;

    for (int i = number - 1; i > 1; i--) {
        if (number % i == 0) {
            number = i;
        }
    }
    return number;
}

Простой фактор с использованием сита :

#include <bits/stdc++.h>
using namespace std;
#define N 10001  
typedef long long ll;
bool visit[N];
vector<int> prime;

void sieve()
{
            memset( visit , 0 , sizeof(visit));
            for( int i=2;i<N;i++ )
            {
                if( visit[i] == 0)
                {
                    prime.push_back(i);
                    for( int j=i*2; j<N; j=j+i )
                    {
                        visit[j] = 1;
                    }
                }
            }   
}
void sol(long long n, vector<int>&prime)
{
            ll ans = n;
            for(int i=0; i<prime.size() || prime[i]>n; i++)
            {
                while(n%prime[i]==0)
                {
                    n=n/prime[i];
                    ans = prime[i];
                }
            }
            ans = max(ans, n);
            cout<<ans<<endl;
}
int main() 
{
           ll tc, n;
           sieve();

           cin>>n;
           sol(n, prime);

           return 0;
}

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

Кроме того, предыдущий ответ, предполагающий сито Эратосфена, совершенно неверен. Я только что написал две программы для factor 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

Эта версия была в 90 раз быстрее сита.

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

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

Сначала вычислите список простых чисел, например 2 3 5 7 11 13 ...

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

С Java:

Для значений int :

public static int[] primeFactors(int value) {
    int[] a = new int[31];
    int i = 0, j;
    int num = value;
    while (num % 2 == 0) {
        a[i++] = 2;
        num /= 2;
    }
    j = 3;
    while (j <= Math.sqrt(num) + 1) {
        if (num % j == 0) {
            a[i++] = j;
            num /= j;
        } else {
            j += 2;
        }
    }
    if (num > 1) {
        a[i++] = num;
    }
    int[] b = Arrays.copyOf(a, i);
    return b;
}

Для значений long :

static long[] getFactors(long value) {
    long[] a = new long[63];
    int i = 0;
    long num = value;
    while (num % 2 == 0) {
        a[i++] = 2;
        num /= 2;
    }
    long j = 3;
    while (j <= Math.sqrt(num) + 1) {
        if (num % j == 0) {
            a[i++] = j;
            num /= j;
        } else {
            j += 2;
        }
    }
    if (num > 1) {
        a[i++] = num;
    }
    long[] b = Arrays.copyOf(a, i);
    return b;
}

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

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

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

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

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

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

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