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

Question

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

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

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

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

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

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

Answer 1

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

Answer 2

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

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

Answer 3

Следующий алгоритм 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;
 }

Answer 4

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

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

Answer 5

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

Answer 6

Вычисляет наибольший простой множитель числа, используя рекурсию в 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
}

Answer 7

#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

Answer 8

Мне кажется, что шаг №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 раз быстрее сита.

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

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

Answer 9

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

Answer 10

Вот моя попытка в 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;
    }

  }
}