Largest Prime Factor Python

Question

Я пытаюсь найти самый большой простой коэффициент заданного числа (600851475143) с помощью Python. Я сделал следующий код, но проблема в том, что он берет навсегда, возможно, потому, что он выполняет итерацию по спискам миллионы раз. Как оптимизировать этот процесс?

def factors(n): 
    list = [] 
    i = 1 
    while i < n: 
     if n % i == 0: 
      list.append(i) 
     i += 1 
    return list 

def prime(n): 
    list = factors(n) 
    primelist = [] 
    for item in list[1:]: 
     if item % 2 != 0 and item % 3 != 0 and item % 4 != 0 and item \ 
     % 5 != 0 and item % 6 != 0 and item % 7 != 0 and item % 8 != 0 \ 
     and item % 9 != 0: 
      primelist.append(item) 
    return primelist 

def greatestprime(n): 
    list = prime(n) 
    list[0] = lnum 
    i = 1 
    while i < len(list): 
     if list[i] > lnum: 
      lnum = list[i] 
    return lnum 

#print(greatestprime(600851475143)) 

Answer 1

Если вы только факторизующие единственное число n, то наивный подход тестирования каждого числа от 2 до sqrt(n) (квадратного корня из n) должен дать результат быстро для чисел до 10 . Вы пишете больше кода, чем необходимо.

Немного лучше всего подходит бы:

• Тест 2, затем проверить каждый нечетный номер
• Test 2, 3, 5, затем проверить все целые числа вида 6k + 1 и 6k + 5, где К > = 1
• 2 подхода выше: wheel factorization с n = 2 и n = 2 * 3 = 6 соответственно. Вы можете поднять его до n = 2 * 3 * 5 * 7 = 210 (выше не приносит большой эффективности).

Чувствительно лучший подход состоит в том, чтобы сгенерировать простые числа через сито и испытание (без избыточного теста) Eratosthenes. Есть даже лучшие подходы, такие как факторизация Pollard's rho, но оба метода являются излишними, если вы не работаете с большим количеством чисел.

Answer 2

Нахождение наибольшего первичного коэффициента числа действительно не так сложно, как люди делают это.

from itertools import takewhile 
from math import floor, sqrt 

def _prime_numbers_helper(): 
    yield 2 
    yield 3 
    i = 1 
    while True: 
     yield 6 * i - 1 
     yield 6 * i + 1 
     i += 1 

def prime_numbers(ceiling=None): 
    if ceiling is None: 
     yield from _prime_numbers_helper() 
    else: 
     yield from takewhile(lambda number: number <= ceiling, _prime_numbers_helper()) 

def largest_prime_factor(number): 
    if number % int(number) != 0: 
     raise ValueError('The number must be an integer.') 
    if number in (0, 1): 
     raise ValueError('There is no largest prime factor of {}.'.format(number)) 

    while True: 
     for i in prime_numbers(floor(sqrt(abs(number)))): 
      if number % i == 0: 
       number //= i 
       break 
     else: 
      return number 

else выражения выполняется только тогда, когда выражение выполняется for к завершению (то есть, когда число не может быть разложено дальше).

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

Обратите внимание, что это предполагает, что вы используете Python 3.3 или новее.

Из любопытства это для Project Euler Problem 3?

Answer 3

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

function factors(n) 
    f, fs := 2, [] 
    while f * f <= n 
     while n % f == 0 
      n := n/f 
      fs := f :: fs 
     f := f + 1 
    if n <> 1 
     n :: fs 
    return reverse(fs) 

Если вы заинтересованы в программировании с простыми числами, или если вы ищете для библиотеки, чтобы помочь с проектом проблемы Эйлера, которые включают простые числа, я скромно рекомендую this essay в моем блоге, который включает в себя, среди прочего, перевода выше псевдокода на Python:

def td_factors(n, limit=1000000): 
    if type(n) != int and type(n) != long: 
     raise TypeError('must be integer') 
    fs = [] 
    while n % 2 == 0: 
     fs += [2] 
     n /= 2 
    if n == 1: 
     return fs 
    f = 3 
    while f * f <= n: 
     if limit < f: 
      raise OverflowError('limit exceeded') 
     if n % f == 0: 
      fs += [f] 
      n /= f 
     else: 
      f += 2 
    return fs + [n] 

Answer 4

Фактической Окончательной программа: Использует столбик старого способ найти факторы и сохраняет только наибольший/текущий коэффициент до тех пор, пока не будет найден последний.

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

def prime_factors_old_fashioned_factorization(number): 
    y=1 
    for x in range(2,number): 
     if(number%x==0): 
      print("number=",number,"\t and X=",x) 
      while(number%x==0): 
       print("number=",number) 
       number=number/x 
      print("new number=",number) 
      y=x 
      x=x+1 
      if((number==1) or (number<x)): 
       break; 
    print("largest prime factor=",y) 

Answer 5

Здесь 2 возможности. Один из this blog:

def gpf(n): 
    """ 
    Find the greatest prime factor of n 
    """ 
    if n < 2: 
     raise ValueError('{} does not have a prime factorization'.format(n)) 
    divisor = 2 
    while n > 1: 
     if not n % divisor: 
      n /= divisor 
      divisor -= 1 
     divisor += 1 
    return divisor 

ваш пример:

In [15]: gpf(600851475143) 
Out[15]: 6857 

In [16]: timeit gpf(600851475143) 
1000 loops, best of 3: 1.55 ms per loop 

или с использованием SymPy библиотеки:

from sympy import factorint 
def gpf(n): 
    return max(factorint(n).keys()) 

(обратите внимание, что это определено поведение при п < 2)

Answer 6

Этот как я пошел об этом:

def is_prime(m): 
    """Checks if the argument is a prime number.""" 

    if m < 2: return False 

    for i in xrange(2, m): 
     if m % i == 0: 
      return False 

    return True 

def get_largest_prime_factor(k): 
    """Gets the largest prime factor for the argument.""" 

    prime_divide = (p for p in xrange(1, k)) 
    for d in prime_divide: 

     if k % d == 0 and is_prime(k/d): 
      return k/d 

print get_largest_prime_factor(600851475143) 

Answer 7

Try:

number = whatever your number is 
divisor = 2 

while divisor < number: 
    if number % divisor == 0: 
     number /= divisor 
    else: 
     divisor += 1 

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

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

Другой полезный эвристический найти квадратный корень из своего номера, и только проверить число меньше, чем: это невозможно n > sqrt(number) для n, которые (целое число) факторы number. Однако мне нравится первый метод.

sike, не видел, что кто-то уже опубликовал действительно подобное решение.