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

Ответ 1

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

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

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

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

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

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

Ответ 2

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

Ответ 3

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

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

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

Ответ 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);

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

Ответ 5

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

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

largest_prime_factor(600851475143)
# => 6857

Ответ 6

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

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

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 [email protected](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, но алгоритм остается тем же.

Ответ 7

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

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

Ответ 8

    //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 prime
                test = 1;
                break;
            }
        }

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

Ответ 9

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

Примечание: Код алгоритма Миллера-Рабина - это адаптированная, слегка улучшенная версия из Rosetta Code. Код был протестирован с использованием Python 2.7.8 и Python 3.4.1

def int_sqrt(n):
    x = n
    y = (x + 1) >> 1
    while y < x:
        x = y
        y = (x + n // x) >> 1
    return x

def is_composite(a, d, n, s):
    if pow(a, d, n) == 1:
        return False
    for i in range(s):
        if pow(a, 2**i * d, n) == n-1:
            return False
    return True # n  is definitely composite

def is_prime(n):
    if n < 5:
        if n == 2 or n == 3:
            return True
        return False
    p = n % 6
    if p != 1 and p != 5:
        return False
    d, s = n - 1, 0
    while not d % 2:
        d, s = d >> 1, s + 1
    if n < 2047: 
        return not is_composite(2, d, n, s)
    if n < 1373653: 
        return not any(is_composite(a, d, n, s) for a in (2, 3))
    if n < 9080191: 
        return not any(is_composite(a, d, n, s) for a in (31, 73))
    if n < 25326001: 
        return not any(is_composite(a, d, n, s) for a in (2, 3, 5))
    if n < 118670087467: 
        if n == 3215031751: 
            return False
        return not any(is_composite(a, d, n, s) for a in (2, 3, 5, 7))
    if n < 2152302898747: 
        return not any(is_composite(a, d, n, s) for a in (2, 3, 5, 7, 11))
    if n < 3474749660383: 
        return not any(is_composite(a, d, n, s) for a in (2, 3, 5, 7, 11, 13))
    if n < 341550071728321: 
        return not any(is_composite(a, d, n, s) for a in (2, 3, 5, 7, 11, 13, 17))
    if n < 3825123056546413051: 
        return not any(is_composite(a, d, n, s) for a in (2, 3, 5, 7, 11, 13, 17, 19, 23))
    return not any(is_composite(a, d, n, s) for a in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53))

def factorize(n):
    factors = []
    if n < 2: return factors
    if is_prime(n):
        factors.append(n)
        return factors
    while n % 2 == 0:
        n >>= 1
        factors.append(2)
    if n == 1: return factors
    max = int_sqrt(n) + 1
    i = 3
    while i < max:
        while n % i == 0:
            n = n // i
            factors.append(i)
        if n == 1: return factors
        if is_prime(n):
            factors.append(n)
            return factors
        i += 2
    return []

print(factorize(98768765456789876))

Вывод:

[2, 2, 7, 23, 153367648224829]

Ответ 10

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)

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

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

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

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

Ответ 11

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

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

Ответ 12

Инициативный подход 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

Ответ 13

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

Мое решение в 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 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

Ответ 14

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

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

  }
}

Ответ 15

#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

Ответ 16

Вычисляет наибольший простой коэффициент числа с использованием рекурсии в С++. Ниже приведен порядок работы кода:

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
}

Ответ 17

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

Ответ 18

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

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

Ответ 19

Нашел это решение в Интернете "Джеймс Ванг",

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

Ответ 20

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

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

Ответ 21

Мне кажется, что шаг № 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

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

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

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

Ответ 22

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

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

Ответ 23

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

Ответ 24

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

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

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

Ответ 25

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

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

Ответ 26

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

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

Ответ 27

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

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

max prime можно найти, используя:

n= 373764623
max(primes(n))

и список найденных факторов, используя:

list(primes(n))

Ответ 28

#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();
 }