숫자의 모든 제수를 구하는 가장 좋은 방법은 무엇입니까?
다음은 매우 멍청한 방법입니다.
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
'Programing' 카테고리의 다른 글
django-storages 및 Amazon S3를 사용하지만 정적 파일 및 미디어 파일에 대해 다른 폴더를 사용하여 Django 프로젝트를 설정하는 방법은 무엇입니까? (0) | 2020.09.05 |
---|---|
Windows 8.1의 고해상도 화면에서 Eclipse 인터페이스 아이콘이 매우 작음 (0) | 2020.09.05 |
추상 클래스와 특성의 차이점 (0) | 2020.09.05 |
테이블에 Lua의 요소가 포함되어 있는지 확인하는 방법은 무엇입니까? (0) | 2020.09.05 |
RPC 프레임 워크와 Apache Thrift 란 무엇입니까? (0) | 2020.09.05 |