숫자의 모든 나누기를 얻는 가장 좋은 방법은 무엇입니까?
아주 멍청한 방법은 다음과 같습니다.
def divisorGenerator(n):
for i in xrange(1,n/2+1):
if n%i == 0: yield i
yield n
제가 얻고 싶은 결과는 이것과 비슷하지만, 저는 더 똑똑한 알고리즘을 원합니다(이 알고리즘은 너무 느리고 멍청합니다 :-)
저는 주요 요인과 그 다양성을 충분히 빠르게 찾을 수 있습니다.다음과 같은 방식으로 요인을 생성하는 생성기가 있습니다.
1,도 1계수 1, 계수 1)
2, 2계수 2, 계수 2)
3, 3변수 3, 변수 3)
등등...
즉, 의 산출물
for i in factorGenerator(100):
print i
다음과 같습니다.
(2, 2)
(5, 2)
이것이 내가 하고 싶은 일에 얼마나 유용한지 모르겠습니다(다른 문제를 위해 코딩했습니다). 어쨌든 더 현명한 방법을 만들고 싶습니다.
for i in divisorGen(100):
print i
출력:
1
2
4
5
10
20
25
50
100
업데이트: 그렉 휴길과 그의 "똑똑한 방법" 덕분입니다 :) 100000000의 모든 나눗셈을 계산하는 것은 그 멍청한 방법이 내 기계에 취한 39에 대한 그의 방법으로 0.01초가 걸렸습니다, 매우 멋집니다 :D.
업데이트 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, 즉 '어려운' 문제입니다.철저한 검색은 여러분이 하는 방식으로, 확실한 답을 얻는 것만큼 좋습니다.이 사실은 암호화 알고리즘 등에서 보안을 위해 사용됩니다.만약 누군가가 이 문제를 해결한다면, 우리의 현재 '보안된' 통신의 대부분은 안전하지 않을 것입니다.
파이썬 코드:
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]
에 들르셔도 될 것 같습니다.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의 모든 지수가 채워집니다.
출처: 숫자의 약수를 구하는 방법
이미 많은 해결책이 있지만, 저는 정말 이것을 게시해야 합니다 :)
이것은 다음과 같습니다.
- 읽기 쉬운
- 짧다
- 자체 포함, 복사 및 붙여넣기 준비
- 빠른 (주요 요인과 지수가 많은 경우, 허용된 솔루션보다 > 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
예시적인 Pythonic 원라이너:
from itertools import chain
from math import sqrt
def divisors(n):
return set(chain.from_iterable((i,n//i) for i in range(1,int(sqrt(n))+1) if n%i == 0))
하지만 더 좋은 것은 그냥 sympy를 사용하는 것입니다.
from sympy import divisors
나는 그렉 솔루션을 좋아하지만, 좀 더 파이썬 같은 솔루션이었으면 좋겠습니다.저는 그것이 더 빠르고 더 읽기 쉬울 것이라고 생각합니다. 그래서 저는 얼마간의 코딩 끝에 이것을 만들었습니다.
목록의 데카르트 곱을 만들려면 처음 두 함수가 필요합니다.그리고 이 문제가 발생할 때마다 재사용할 수 있습니다.그런데, 제가 직접 프로그래밍을 해야만 했습니다. 이 문제에 대한 표준 해결책을 아시는 분이 있다면 언제든지 연락 주시기 바랍니다.
이제 "요인 생성기"가 사전을 반환합니다.그런 다음 사전을 "divisors"에 입력하고, 사전을 사용하여 먼저 목록 목록을 생성합니다. 여기서 각 목록은 p 소수가 있는 p^n 형식의 요인 목록입니다.그런 다음 우리는 그 목록의 데카르트 곱을 만들고, 마지막으로 그렉의 솔루션을 사용하여 제수를 생성합니다.우리는 그것들을 분류하고 돌려줍니다.
제가 테스트해봤는데 이전 버전보다 조금 빠른 것 같습니다.더 큰 프로그램의 일환으로 테스트를 해봤기 때문에 어느 정도 속도가 빠른지는 잘 모르겠습니다.
피에트로 스페로니 (피에트로스페로니 도트 잇)
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)
추신: 제가 스택 오버플로에 글을 올리는 것은 처음입니다.저는 어떤 피드백도 기대하고 있습니다.
여기 순수 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))
PC에 메모리가 너무 많은 경우 다음과 같이 numpy를 사용하여 한 줄로 묶는 속도가 충분히 빠릅니다.
N = 10000000; tst = np.arange(1, N); tst[np.mod(N, tst) == 0]
Out:
array([ 1, 2, 4, 5, 8, 10, 16,
20, 25, 32, 40, 50, 64, 80,
100, 125, 128, 160, 200, 250, 320,
400, 500, 625, 640, 800, 1000, 1250,
1600, 2000, 2500, 3125, 3200, 4000, 5000,
6250, 8000, 10000, 12500, 15625, 16000, 20000,
25000, 31250, 40000, 50000, 62500, 78125, 80000,
100000, 125000, 156250, 200000, 250000, 312500, 400000,
500000, 625000, 1000000, 1250000, 2000000, 2500000, 5000000])
느린 PC에서는 1초 미만 걸립니다.
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
참고: 지원하는 언어의 경우 꼬리 재귀적일 수 있습니다.
#slow but pretty
return [x for x in range(1,n+1) if n/x==int(n/x)]
이 경우를 가정하면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)
제너레이터 기능을 통한 솔루션은 다음과 같습니다.
def divisor(num):
for x in range(1, num + 1):
if num % x == 0:
yield x
while True:
yield None
주어진 숫자의 제곱근을 계산한 다음 범위(1,square_root+1)를 반복합니다.
number = int(input("Enter a Number: "))
square_root = round(number ** (1.0 / 2))
print(square_root)
divisor_list = []
for i in range(1,square_root+1):
if number % i == 0: # Check if mod return 0 if yes then append i and number/i in the list
divisor_list.append(i)
divisor_list.append(int(number/i))
print(divisor_list)
def divisorGen(n): v = n last = [] for i in range(1, v+1) : if n % i == 0 : last.append(i)
저는 이 문제에 대해 왜 그렇게 많은 복잡한 해결책이 있는지 이해할 수 없습니다.
다음은 제 생각입니다.
def divisors(n):
lis =[1]
s = math.ceil(math.sqrt(n))
for g in range(s,1, -1):
if n % g == 0:
lis.append(g)
lis.append(int(n / g))
return (set(lis))
언급URL : https://stackoverflow.com/questions/171765/what-is-the-best-way-to-get-all-the-divisors-of-a-number
'code' 카테고리의 다른 글
| Oracle SQL Developer에서 Refursor 결과/출력을 확인하는 방법은 무엇입니까? (0) | 2023.08.01 |
|---|---|
| 쿠버네츠에서 포드를 멈추는 방법 (0) | 2023.08.01 |
| sql plus의 문자열에서 마지막 문자 제거 (0) | 2023.08.01 |
| ID 선택기에 jQuery 도트가 있습니까? (0) | 2023.08.01 |
| Switch 문 외부의 Swift 열거형 관련 값에 액세스하는 방법 (0) | 2023.08.01 |