Первичная факторизация - список

Ответ 1

Простейшее пробное деление:

def primes(n):
    primfac = []
    d = 2
    while d*d <= n:
        while (n % d) == 0:
            primfac.append(d)  # supposing you want multiple factors repeated
            n //= d
        d += 1
    if n > 1:
       primfac.append(n)
    return primfac

с O(sqrt(n)) сложностью (в худшем случае). Вы можете легко улучшить его специальным корпусом 2 и зацикливать только на нечетные d (или специальные корпуса с более малыми штрихами и зацикливание на меньшее количество возможных делителей).

Ответ 2

Это решение на основе понимания, оно может быть самым близким к рекурсивному решению на Python, которое можно использовать для больших чисел.

Вы можете получить правильные делители с одной строкой:

divisors = [ d for d in xrange(2,int(math.sqrt(n)) if n % d == 0 ]

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

def isprime(d): return all( d % od != 0 for od in divisors if od != d )

который проверяет, что никакие другие делители не делят d.

Тогда мы можем отфильтровать простые делители:

prime_divisors = [ d for d in divisors if isprime(d) ]

Конечно, его можно объединить в одну функцию:

def primes(n):
    divisors = [ d for d in range(2,n//2+1) if n % d == 0 ]
    return [ d for d in divisors if \
             all( d % od != 0 for od in divisors if od != d ) ]

Здесь существует \, чтобы разбить строку, не впуская с отступом Python.

Ответ 3

Модуль primefac делает факторизации со всеми фантастическими методами, которые математики развивали на протяжении веков:

#!python

import primefac
import sys

n = int( sys.argv[1] )
factors = list( primefac.primefac(n) )
print '\n'.join(map(str, factors))

Ответ 4

Большинство вышеупомянутых решений выглядят несколько неполными. Первичная факторизация повторила бы каждый простой коэффициент числа (e.g. 9 = [3 3]).

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

Использование sieve Of Eratosthenes для поиска простых чисел для тестирования является оптимальным, но; вышеупомянутая реализация использовала больше памяти, чем необходимо.

Я не уверен, что если "wheel factorization" будет превосходить применение простых факторов, для тестов деления n.

Хотя это решение действительно полезно, я бы предложил следующие две функции -

Функция-1:

def primes(n):
    if n < 2: return
    yield 2
    plist = [2]
    for i in range(3,n):
        test = True
        for j in plist:
            if j>n**0.5:
                break
            if i%j==0:
                test = False
                break
        if test:
            plist.append(i)
            yield i

Функция-2:

def pfactors(n):
    for p in primes(n):
        while n%p==0:
            yield p
            n=n//p
            if n==1: return

list(pfactors(99999))
[3, 3, 41, 271]

3*3*41*271
99999

list(pfactors(13290059))
[3119, 4261]

3119*4261
13290059

Ответ 5

Вот моя версия факторизации методом пробного деления, которая включает в себя оптимизацию деления только на два и нечетные целые числа, предложенные Даниэлем Фишером:

def factors(n):
    f, fs = 3, []
    while n % 2 == 0:
        fs.append(2)
        n /= 2
    while f * f <= n:
        while n % f == 0:
            fs.append(f)
            n /= f
        f += 2
    if n > 1: fs.append(n)
    return fs

Улучшение деления на два и нечетные числа - это факторизация колес, которая использует циклический набор разрывов между потенциальными числами, чтобы значительно уменьшить количество пробных подразделений. Здесь мы используем 2,3,5-колесо:

def factors(n):
    gaps = [1,2,2,4,2,4,2,4,6,2,6]
    length, cycle = 11, 3
    f, fs, next = 2, [], 0
    while f * f <= n:
        while n % f == 0:
            fs.append(f)
            n /= f
        f += gaps[next]
        next += 1
        if next == length:
            next = cycle
    if n > 1: fs.append(n)
    return fs

Таким образом, print factors(13290059) выведет [3119, 4261]. Факторинговые колеса имеют одинаковую сложность времени O (sqrt (n)) как нормальное пробное деление, но на практике будут в два-три раза быстрее.

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

Ответ 6

def get_prime_factors(number):
    """
    Return prime factor list for a given number
        number - an integer number
        Example: get_prime_factors(8) --> [2, 2, 2].
    """
    if number == 1:
        return []

    # We have to begin with 2 instead of 1 or 0
    # to avoid the calls infinite or the division by 0
    for i in xrange(2, number):
        # Get remainder and quotient
        rd, qt = divmod(number, i)
        if not qt: # if equal to zero
            return [i] + get_prime_factors(rd)

    return [number]

Ответ 7

Я настроил @user448810 ответ, чтобы использовать итераторы из itertools (и python3.4, но он должен быть обратным). Решение на 15% быстрее.

import itertools

def factors(n):
    f = 2
    increments = itertools.chain([1,2,2], itertools.cycle([4,2,4,2,4,6,2,6]))
    for incr in increments:
        if f*f > n:
            break
        while n % f == 0:
            yield f
            n //= f
        f += incr
    if n > 1:
        yield n

Обратите внимание, что это возвращает итерируемый, а не список. Оберните его в список(), если это вам нужно.

Ответ 8

простые множители числа:

def primefactors(x):
    factorlist=[]
    loop=2
    while loop<=x:
        if x%loop==0:
            x//=loop
            factorlist.append(loop)
        else:
            loop+=1
    return factorlist

x = int(input())
alist=primefactors(x)
print(alist)

Вы получите список. Если вы хотите получить пары простых множителей числа, попробуйте следующее: http://pythonplanet.blogspot.in/2015/09/list-of-all-unique-pairs-of-prime.html

Ответ 9

Вы можете использовать sieve Of Eratosthenes для генерации всех простых чисел до (n/2) + 1, а затем использовать понимание списка, чтобы получить все основные факторы

def rwh_primes2(n):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    """ Input n>=6, Returns a list of primes, 2 <= p < n """
    correction = (n%6>1)
    n = {0:n,1:n-1,2:n+4,3:n+3,4:n+2,5:n+1}[n%6]
    sieve = [True] * (n/3)
    sieve[0] = False
    for i in xrange(int(n**0.5)/3+1):
      if sieve[i]:
        k=3*i+1|1
        sieve[      ((k*k)/3)      ::2*k]=[False]*((n/6-(k*k)/6-1)/k+1)
        sieve[(k*k+4*k-2*k*(i&1))/3::2*k]=[False]*((n/6-(k*k+4*k-2*k*(i&1))/6-1)/k+1)
    return [2,3] + [3*i+1|1 for i in xrange(1,n/3-correction) if sieve[i]]

def primeFacs(n):
    primes = rwh_primes2((n/2)+1)
    return [x for x in primes if n%x == 0]

print primeFacs(99999)
#[3, 41, 271]

Ответ 10

    from sets import Set
    # this function generates all the possible factors of a required number x
    def factors_mult(X):
        L = []
        [L.append(i) for i in range(2,X) if X % i == 0]
        return L

    # this function generates list containing prime numbers upto the required number x 
    def prime_range(X):
        l = [2]
        for i in range(3,X+1):
            for j in range(2,i):
               if i % j == 0:
               break
            else:    
               l.append(i)
        return l

    # This function computes the intersection of the two lists by invoking Set from the sets module
    def prime_factors(X):
        y = Set(prime_range(X))
        z = Set(factors_mult(X))
        k = list(y & z)
        k = sorted(k)

        print "The prime factors of " + str(X) + " is ", k

    # for eg
    prime_factors(356)

Ответ 11

Большая часть ответа делает вещи слишком сложными. Мы можем это сделать

def prime_factors(n):
    num = []

    #add 2 to list or prime factors and remove all even numbers(like sieve of ertosthenes)
    while(n%2 == 0):
        num.append(2)
        n /= 2

    #divide by odd numbers and remove all of their multiples increment by 2 if no perfectlly devides add it
    for i in xrange(3, int(sqrt(n))+1, 2):
        while (n%i == 0):
            num.append(i)
            n /= i

    #if no is > 2 i.e no is a prime number that is only divisible by itself add it
    if n>2:
        num.append(n)

    print (num)

Алгоритм GeeksforGeeks

Ответ 12

Простой способ получить желаемое решение

def Factor(n):
    d = 2
    factors = []
    while n >= d*d:
        if n % d == 0:
            n//=d
            # print(d,end = " ")
            factors.append(d)
        else:
            d = d+1
    if n>1:
        # print(int(n))
        factors.append(n)
    return factors

Ответ 13

def factorize(n):
  for f in range(2,n//2+1):
    while n%f == 0:
      n //= f
      yield f

Он медленный, но мертвый просто. Если вы хотите создать утилиту командной строки, вы можете сделать следующее:

import sys
[print(i) for i in factorize(int(sys.argv[1]))]