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

Question

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

def prime(n):
  i=0;
  while(n!=2):
    for i in range(2,n):
        if(n%i==0):
            prime(n/i);
        else:
            continue;
    print("The highest prime factor is: "),n;

print("Enter a number to find its highest prime factor");
n=input();
prime(n);

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

Answer 1

РЕДАКТИРОВАТЬ: Мне кажется, что я не могу быть ясным без некоторого кода, так что вот, с некоторыми изменениями от вашего:

def prime(n):
  i=2
  while (n%i != 0 and i < n):
    i += 1
  if (i < n):
    return prime (n/i)
  else:
    print("The highest prime factor is: "),n

print("Enter a number to find its highest prime factor")
n=input()
prime(n)

Однако ваш алгоритм не очень эффективен. Например, вы можете рассмотреть возможность использования Rho Полларда, если вы хотите что-то лучше и не долго писать. И даже если вы хотите придерживаться своей идеи, вам не следует делать такие тесты на делимость. Вы можете сначала запустить сито Erathostene, чтобы проверить делимость только на основные факторы. Или даже помните только последний делитель, который вы нашли, чтобы перезапустить алгоритм оттуда, а не от 2.

Например, немного лучший код будет:

def prime(n,a):
  i = a
  while (n%i != 0 and i*i < n):
    i += 1
  if (i*i < n):
    return prime (n/i, i)
  else:
    print("The highest prime factor is: "),n

print("Enter a number to find its highest prime factor")
n=input()
prime(n,2)

Answer 2

Как избежать рекурсивных звонков:

def largest_prime_factor(number):
  if number == 1:
    return 1

  test = 2
  while number > 1:
    if number % test == 0:
      number /= test
    else:
      test += 1

  return test

Answer 3

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

import math

def prime(n):
    for x in range(2, int(math.sqrt(n)) + 1):
        if n % x == 0:
            print n / x
            return prime(n / x)

if __name__ == '__main__':
    prime(898563214300)

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

Answer 4

Я могу остановить ваш код в цикле следующим образом.
Основная проблема с застрявшим в цикле while(n!=2) (или 1 или что-то), что вы не меняете n,
Обратите внимание - это все равно не даст вам простые числа

def prime(n):
  i=0
  if(n==2):
    print "The highest prime factor is 2"
    return
  for i in range(2,n):
      if(n%i==0):
          prime(n/i)
      else:
          continue
  print("The highest prime factor is: "),n

print("Enter a number to find its highest prime factor");
n=input()
prime(n)

Ищите SO с помощью "[python] primes", чтобы найти множество способов сделать это правильно.

Answer 5

Рассмотрим этот фрагмент кода на C, это очень эффективный алгоритм для нахождения наибольшего простого множителя числа.

Функции говорят сами за себя.

int isPrime(long long int n)
{
    long long int i;
    for(i=2;i*i<=n;i++)
        if(n%i==0)
            return 0;
    return 1;
}

long long int findLargestPrimeFactor(long long int n)
{
    long long int counter=2;
    while(n!=1)
    {
        if(isPrime(n))
            return n;
        while(n%counter==0)
            n/=counter;
        counter++;
   }
   return counter-1;
}

Answer 6

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

for($div=2;$div<=sqrt($n);$div++)
{
    if($n%$div==0)
    {
        $n = $n/$div;
        $div--;
    }
}

взяв корень sq, вы избежите ненужного зацикливания.

Answer 7

Один простой (но крайне неэффективный) подход без рекурсии: (извините, пожалуйста, мой синтаксис python).

Предполагая, что isPrime(k) является функцией, которая возвращает true, если k является простым. Это может быть реализовано с использованием сита Эрастосена.

def prime(n):
  i=0;
  largestPrimeFactor = -1;
  for i in range(2,n/2):
     if( isPrime(i) && n%i==0 ) :
         largestPrimeFactor = i;
  print("The highest prime factor is: "),largestPrimeFactor