숫자의 모든 제수를 구하는 가장 좋은 방법은 무엇입니까?

숫자의 모든 제수를 구하는 가장 좋은 방법은 무엇입니까?

---

다음은 매우 멍청한 방법입니다.

def divisorGenerator(n):
    for i in xrange(1,n/2+1):
        if n%i == 0: yield i
    yield n

내가 얻고 싶은 결과는 이것과 비슷하지만 더 똑똑한 알고리즘을 원합니다 (이건 너무 느리고 멍청합니다 :-)

나는 소인수와 그 다중성을 충분히 빠르게 찾을 수 있습니다. 이런 식으로 요소를 생성하는 생성기가 있습니다.

(인수 1, 다중도 1) (인수 2, 다중도 2)
(인수
3, 다중도 3)
등 ...

즉, 출력

for i in factorGenerator(100):
    print i

is :

(2, 2)
(5, 2)

내가 원하는 일에 얼마나 유용한 지 모르겠습니다 (다른 문제에 대해 코딩했습니다) 어쨌든 더 똑똑한 방법을 원합니다.

for i in divisorGen(100):
    print i

이것을 출력하십시오 :

1
2
4
5
10
20
25
50
100

---

업데이트 : Greg Hewgill과 그의 "스마트 한 방법"에게 많은 감사를드립니다 . :) 100000000의 모든 제수를 계산하는 데 0.01 초가 걸렸습니다.

업데이트 2 : 이 게시물 의 중복이라고 말하지 마세요. 주어진 숫자의 제수를 계산할 때 모든 제수를 계산할 필요는 없습니다. 다른 문제입니다. 그렇지 않다고 생각한다면 위키피디아에서 "제수 함수"를 찾으십시오. 게시하기 전에 질문과 답변을 읽으십시오. 주제가 무엇인지 이해하지 못하는 경우 유용하지 않고 이미 제공된 답변을 추가하지 마십시오.

---

factorGenerator 함수가 주어지면 작동해야하는 divisorGen이 있습니다.

def divisorGen(n):
    factors = list(factorGenerator(n))
    nfactors = len(factors)
    f = [0] * nfactors
    while True:
        yield reduce(lambda x, y: x*y, [factors[x][0]**f[x] for x in range(nfactors)], 1)
        i = 0
        while True:
            f[i] += 1
            if f[i] <= factors[i][1]:
                break
            f[i] = 0
            i += 1
            if i >= nfactors:
                return

이 알고리즘의 전반적인 효율성은 전적으로 factorGenerator의 효율성에 달려 있습니다.

---

Shimi가 말한 내용을 확장하려면 1에서 n의 제곱근까지만 루프를 실행해야합니다. 그런 다음 쌍을 찾으려면을 수행하십시오. 그러면 n / i전체 문제 공간이 포함됩니다.

또한 언급했듯이 이것은 NP 또는 '어려운'문제입니다. 철저한 검색은 보장 된 답변을 얻는 것만큼이나 좋습니다. 이 사실은 암호화 알고리즘 등에서 보안을 위해 사용됩니다. 누군가이 문제를 해결한다면 현재의 '안전한'커뮤니케이션이 전부는 아니더라도 대부분은 안전하지 않게 될 것입니다.

Python 코드 :

import math

def divisorGenerator(n):
    large_divisors = []
    for i in xrange(1, int(math.sqrt(n) + 1)):
        if n % i == 0:
            yield i
            if i*i != n:
                large_divisors.append(n / i)
    for divisor in reversed(large_divisors):
        yield divisor

print list(divisorGenerator(100))

다음과 같은 목록을 출력해야합니다.

[1, 2, 4, 5, 10, 20, 25, 50, 100]

---

이것에 대한 많은 해결책이 이미 있지만 정말 이것을 게시해야합니다 :)

이것은 :

• 읽을 수있는
• 짧은
• 자체 포함, 복사 및 붙여 넣기 준비
• 빠름 (소인수와 제수가 많은 경우 허용 된 솔루션보다 10 배 이상 빠름)
• python3, python2 및 pypy 호환

암호:

def divisors(n):
    # get factors and their counts
    factors = {}
    nn = n
    i = 2
    while i*i <= nn:
        while nn % i == 0:
            factors[i] = factors.get(i, 0) + 1
            nn //= i
        i += 1
    if nn > 1:
        factors[nn] = factors.get(nn, 0) + 1

    primes = list(factors.keys())

    # generates factors from primes[k:] subset
    def generate(k):
        if k == len(primes):
            yield 1
        else:
            rest = generate(k+1)
            prime = primes[k]
            for factor in rest:
                prime_to_i = 1
                # prime_to_i iterates prime**i values, i being all possible exponents
                for _ in range(factors[prime] + 1):
                    yield factor * prime_to_i
                    prime_to_i *= prime

    # in python3, `yield from generate(0)` would also work
    for factor in generate(0):
        yield factor

---

math.sqrt(n)n / 2 대신에 멈출 수 있다고 생각합니다 .

쉽게 이해할 수 있도록 예를 들어 드리겠습니다. 지금은 sqrt(28)이다 5.29그래서 ceil(5.29)그때 나는 모든 약수를 얻을 수있는 것이다 6시에 중단됩니다 6. 그래서 일 것이다. 어떻게?

먼저 코드를 확인한 다음 이미지를 확인합니다.

import math
def divisors(n):
    divs = [1]
    for i in xrange(2,int(math.sqrt(n))+1):
        if n%i == 0:
            divs.extend([i,n/i])
    divs.extend([n])
    return list(set(divs))

이제 아래 이미지를 참조하십시오.

수 있습니다 내가 이미 추가 한 말을 1내 제수 목록에 내가 시작 i=2그래서

따라서 모든 반복이 끝날 때 몫과 제수를 목록에 추가하면 28의 모든 제수가 채워집니다.

출처 : 숫자의 제수를 결정하는 방법

---

나는 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에 게시하는 것은 처음입니다. 피드백을 기다리고 있습니다.

---

CodeReview 에서 채택한 다음은 num=1!

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))

---

오래된 질문이지만 여기에 내 의견이 있습니다.

def divs(n, m):
    if m == 1: return [1]
    if n % m == 0: return [m] + divs(n, m - 1)
    return divs(n, m - 1)

다음으로 프록시 할 수 있습니다.

def divisorGenerator(n):
    for x in reversed(divs(n, n)):
        yield x

참고 : 지원하는 언어의 경우 꼬리 재귀적일 수 있습니다.

---

다음은 순수 Python 3.6에서 최대 10 ** 16의 숫자에 대해 스마트하고 빠른 방법입니다.

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))

---

나는 향후 참조를 위해 Anivarth의 약간 수정 된 버전 (가장 비단뱀이라고 생각하는)을 추가 할 것입니다.

from math import sqrt

def divisors(n):
    divs = {1,n}
    for i in range(2,int(sqrt(n))+1):
        if n%i == 0:
            divs.update((i,n//i))
    return divs

---

factors함수가 n 의 인수를 반환 한다고 가정하면 (예를 들어 factors(60)[2, 2, 3, 5] 목록을 반환) n 의 제수를 계산하는 함수는 다음과 같습니다.

function divisors(n)
    divs := [1]
    for fact in factors(n)
        temp := []
        for div in divs
            if fact * div not in divs
                append fact * div to temp
        divs := divs + temp
    return divs

---

여기 내 해결책이 있습니다. 바보 같지만 잘 작동합니다 ... 모든 적절한 제수를 찾으려고 했으므로 루프가 i = 2에서 시작되었습니다.

import math as m 

def findfac(n):
    faclist = [1]
    for i in range(2, int(m.sqrt(n) + 2)):
        if n%i == 0:
            if i not in faclist:
                faclist.append(i)
                if n/i not in faclist:
                    faclist.append(n/i)
    return facts

---

목록 이해력 사용에만 관심이 있고 다른 것은 중요하지 않은 경우!

from itertools import combinations
from functools import reduce

def get_devisors(n):
    f = [f for f,e in list(factorGenerator(n)) for i in range(e)]
    fc = [x for l in range(len(f)+1) for x in combinations(f, l)]
    devisors = [1 if c==() else reduce((lambda x, y: x * y), c) for c in set(fc)]
    return sorted(devisors)

---

return [x for x in range(n+1) if n/x==int(n/x)]

---

나를 위해 이것은 잘 작동하고 깨끗합니다 (Python 3)

def divisors(number):
    n = 1
    while(n<number):
        if(number%n==0):
            print(n)
        else:
            pass
        n += 1
    print(number)

매우 빠르지는 않지만 원하는대로 줄 단위로 제수를 반환합니다. 또한 원하는 경우 list.append (n) 및 list.append (number)를 수행 할 수도 있습니다.

참고 URL : https://stackoverflow.com/questions/171765/what-is-the-best-way-to-get-all-the-divisors-of-a-number