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

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

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

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

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

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

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
    }

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

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

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

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

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

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

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

1. возьмите список всех простых чисел в порядке возрастания (см. выше).
2. пусть p быть главным в этом списке, и ps быть основными факторами n/p (см. Шаг 1).
   • если p квадрат больше, чем наше число n, потом n премьер. Мы закончили.
   • если p делит n, тогда p - главный фактор n. Другими факторами являются ps.
   • иначе p не является простым фактором 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 = 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) как нет Прайм, и использовать цикл while вместо.
• установите i на следующее простое число в список.

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

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

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

итерационный подход 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 данного алгоритма не будет эффективным подходом. У вас нет никаких разумных ожиданий, что это просто.

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)

Edit: в шаге 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;
    }

здесь такая же функция@триптих обеспеченная как генератор, который также был упрощен немножко.

def primes(n):
    d = 2
    while (n > 1):
        while (n%d==0):
            yield d
            n /= d
        d += 1

максимальное простое число может быть найдено с помощью:

n= 373764623
max(primes(n))

и список факторов, используя:

list(primes(n))

#include<stdio.h>
#include<conio.h>
#include<math.h>
#include <time.h>

factor(long int n)
{
long int i,j;
while(n>=4)
 {
if(n%2==0) {  n=n/2;   i=2;   }

 else
 { i=3;
j=0;
  while(j==0)
  {
   if(n%i==0)
   {j=1;
   n=n/i;
   }
   i=i+2;
  }
 i-=2;
 }
 }
return i;
 }

 void main()
 { 
  clock_t start = clock();
  long int n,sp;
  clrscr();
  printf("enter value of n");
  scanf("%ld",&n);
  sp=factor(n);
  printf("largest prime factor is %ld",sp);

  printf("Time elapsed: %f\n", ((double)clock() - start) / CLOCKS_PER_SEC);
  getch();
 }