algorithm

나는 Greg 솔루션을 좋아하지만 파이썬처럼 더 좋았 으면 좋겠다. 더 빠르고 가독성이 좋을 것 같습니다. 그래서 얼마간의 코딩 후에 나는 이것을 나왔습니다.

처음 두 함수는 목록의 데카르트 곱을 만드는 데 필요합니다. 그리고이 문제가 발생할 때마다 재사용 할 수 있습니다. 그건 그렇고,이 문제에 대한 표준 솔루션을 아는 사람이 있으면 저에게 연락 주시기 바랍니다.

“Factorgenerator”는 이제 사전을 반환합니다. 그런 다음 사전은 “제수”에 입력되어 먼저 목록 목록을 생성하는 데 사용합니다. 여기서 각 목록은 p 소수를 갖는 p ^ n 형식의 인수 목록입니다. 그런 다음 해당 목록의 데카르트 곱을 만들고 마지막으로 Greg의 솔루션을 사용하여 제수를 생성합니다. 우리는 그들을 분류하고 반환합니다.

나는 그것을 테스트했으며 이전 버전보다 조금 더 빠른 것 같습니다. 더 큰 프로그램의 일부로 테스트했기 때문에 얼마나 더 빠른지 말할 수는 없습니다.

Pietro Speroni (pietrosperoni dot it)

from math import sqrt


##############################################################
### cartesian product of lists ##################################
##############################################################

def appendEs2Sequences(sequences,es):
    result=[]
    if not sequences:
        for e in es:
            result.append([e])
    else:
        for e in es:
            result+=[seq+[e] for seq in sequences]
    return result


def cartesianproduct(lists):
    """
    given a list of lists,
    returns all the possible combinations taking one element from each list
    The list does not have to be of equal length
    """
    return reduce(appendEs2Sequences,lists,[])

##############################################################
### prime factors of a natural ##################################
##############################################################

def primefactors(n):
    '''lists prime factors, from greatest to smallest'''
    i = 2
    while i<=sqrt(n):
        if n%i==0:
            l = primefactors(n/i)
            l.append(i)
            return l
        i+=1
    return [n]      # n is prime


##############################################################
### factorization of a natural ##################################
##############################################################

def factorGenerator(n):
    p = primefactors(n)
    factors={}
    for p1 in p:
        try:
            factors[p1]+=1
        except KeyError:
            factors[p1]=1
    return factors

def divisors(n):
    factors = factorGenerator(n)
    divisors=[]
    listexponents=[map(lambda x:k**x,range(0,factors[k]+1)) for k in factors.keys()]
    listfactors=cartesianproduct(listexponents)
    for f in listfactors:
        divisors.append(reduce(lambda x, y: x*y, f, 1))
    divisors.sort()
    return divisors



print divisors(60668796879)

추신 내가 stackoverflow에 게시하는 것은 처음입니다. 피드백을 기다리고 있습니다.

답변

from itertools import compress

def primes(n):
    """ Returns  a list of primes < n for n > 2 """
    sieve = bytearray([True]) * (n//2)
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i//2]:
            sieve[i*i//2::i] = bytearray((n-i*i-1)//(2*i)+1)
    return [2,*compress(range(3,n,2), sieve[1:])]

def factorization(n):
    """ Returns a list of the prime factorization of n """
    pf = []
    for p in primeslist:
      if p*p > n : break
      count = 0
      while not n % p:
        n //= p
        count += 1
      if count > 0: pf.append((p, count))
    if n > 1: pf.append((n, 1))
    return pf

def divisors(n):
    """ Returns an unsorted list of the divisors of n """
    divs = [1]
    for p, e in factorization(n):
        divs += [x*p**k for k in range(1,e+1) for x in divs]
    return divs

n = 600851475143
primeslist = primes(int(n**0.5)+1)
print(divisors(n))

from itertools import product
import operator

def prod(ls):
   return reduce(operator.mul, ls, 1)

def powered(factors, powers):
   return prod(f**p for (f,p) in zip(factors, powers))


def divisors(num) :

   pf = dict(prime_factors(num))
   primes = pf.keys()
   #For each prime, possible exponents
   exponents = [range(i+1) for i in pf.values()]
   return (powered(primes,es) for es in product(*exponents))