파이썬 약수 모듈 - paisseon yagsu modyul

코딩테스트를 보면 항상 약수 구하는 문제가 나오는 것 같다...

(몇 번 안봤지만...)

그래서 머리에 완전 박히도록 복습을 해본다.

​

우선 약수를 구하는 방법은

n 을 나누었을 때 나머지가 0인 것을 약수라 한다.

예를 들어 20 의 약수라 하면

20 % 1 == 0

20을 1로 나눈 나머지가 0인 경우 약수이다.

먼저 약수를 구하기 위해 입력 받은 수까지 반복문을 돌립니다.

여기서 num+1 을 하는 이유는 1 부터 20보다 작을 때까지이니 20은 반복하지 않기 때문에 +1을 해줍니다

for i in range(1, num+1):

if문으로 20 % 1 == 0 인지 체크를 하고 약수인지 판단을 합니다.

이런 방식으로 코드를 짜면 아래와 같이 나올 수 있습니다.

num = int(input("수? ")) for i in range(1, num+1): if num % i == 0: # 약수임 print(i, end=' ') print()

문제

1 이상의 자연수 N이 주어졌을 때, N의 약수 구하기

풀이

단순한 풀이 방법

def getMyDivisor(n): divisorsList = [] for i in range(1, n + 1): if (n % i == 0) : divisorsList.append(i) return divisorsList

• for 문을 이용해 범위를 약수가 될 수 있는 최솟값인 1부터 최댓값인 자기 자신까지 돌려준다.
• 만약, 나머지가 0이라면 약수라는 뜻이므로 배열에 저장해준다.
• 이 방법을 사용할 경우 작은 수부터 i가 들어가므로 자동으로 오름차순 정렬이 된다.
• 시간 복잡도 : O(N)

더 효율적인 풀이 방법

def getMyDivisor(n): divisorsList = [] for i in range(1, int(n**(1/2)) + 1): if (n % i == 0): divisorsList.append(i) if ( (i**2) != n) : divisorsList.append(n // i) divisorsList.sort() return divisorsList

• N = A * B 로 나타낼 수 있다는 것을 이용한 풀이이다. 항상 약수를 구하면 그 짝이 되는 수가 존재한다. (ex. 6 = 2 * 3 )
• for 문을 이용해 자연수 N의 제곱근까지의 약수를 구하면 그 짝이 되는 약수는 자동으로 구할 수 있다.
• N = A * B 일 때,  A == B 일 수 있기 때문에 (ex. 25 = 5 * 5 ) 값을 중복해서 넣어주지 않기 위해 if 문으로 제곱했을 때 n이 되지 않는지 검사를 해줬다.
  • 혹은 i != (n // i) 로 검사도 가능하다.
• 마지막에 오름차순으로 정렬을 해준 후 return 해주면 된다.
• 시간 복잡도 : O(N^(1/2))

관련 문제

2501번: 약수 구하기

첫째 줄에 N과 K가 빈칸을 사이에 두고 주어진다. N은 1 이상 10,000 이하이다. K는 1 이상 N 이하이다.

www.acmicpc.net

다양한 방법으로 풀어보는것도 재밌는거같다 ㅎㅅㅎ

더 좋은 방법이 있다면 댓글로 알려주세요 !

@미닛메이드 Minnit

파이썬으로 약수(divisor)를 구하는 방법을 살펴보겠습니다.

만들다 보니 여러수를 입력해 공약수와 최대 공약수까지 구하도록 확장시켜 보았습니다.

예를 들면 12의 약수는

• 12를 1(n)부터 12(n)까지 나누기 한 후 나머지가 0이면 n은 약수

• 12 / 1 = 나머지 0 이므로 1은 약수

• 12 / 2 = 나머지 0 이므로 2도 약수...(반복)

 

따라서 12를 나누어 떨어지는 수는 1, 2, 3, 4, 6, 12 입니다.

만약 12와 16의 공약수를 구한다면

• 12의 약수 : 1, 2, 3, 4, 6, 12

• 16의 약수 : 1, 2, 4, 8, 16

• 12와 16의 공약수 : 1, 2, 4

• 따라서, 최대공약수는 4

[여러수의 약수, 공약수, 최대공약수 구하기]

조건 

위 방식을 이용해 아래 미션을 수행해 보았습니다.

• 100,000,000의 약수를 구하라. (일억)

방법 1 :

• 단순하게 1부터 약수를 구하고자 하는 수까지 반복

import time cnt = int(input('약수를 구할 횟수 입력:')) divs = [] for i in range(cnt): n = int(input('숫자 입력:')) d = [] s = time.time() for i in range(1, n+1): if n%i == 0: d.append(i) divs.append(set(d)) print(n,'의 약수 : ', *d, '소요시간 : ', time.time()-s,'(sec)') print() if cnt>1: comdiv = set.intersection(*divs) print('공약수 : ', *comdiv) print('최대 공약수 : ', max(comdiv))

약수는 잘 구해지지만 100,000,000 (1억) 의 약수를 구하니 시간이 너무 오래 걸립니다.

제 컴퓨터가 느려서 그런건 아니고 위 코드는 개선할 수 있는 여지가 많이 보입니다.

• 시간 복잡도 O(n) , 소요시간 약 13초 

방법 2 :

• 12(n)의 약수 1, 2, 3, 4, 6, 12 중 자신을 제외한 가장 큰 약수는 n/2 이므로,

• 12의 반인 6까지만 약수 검사를 진행

import time cnt = int(input('약수를 구할 횟수 입력:')) divs = [] for i in range(cnt): n = int(input('숫자 입력:')) d = [] s = time.time() for i in range(1, n//2+1): if n%i == 0: d.append(i) d.append(n) divs.append(set(d)) print(n,'의 약수 : ', *d, '\n소요시간 : ', time.time()-s,'(sec)') print() if cnt>1: comdiv = set.intersection(*divs) print('공약수 : ', *comdiv) print('최대 공약수 : ', max(comdiv))

방법 1과 비교해 바뀐 부분은 12번 라인 n//2+1 뿐입니다.

파이썬에서 '/' 나누기 연산자를 두번 '//'쓰면 나머지 소수점을 버린 몫을 얻습니다.

예를 들면 5/2 = 2.5 이지만 5//2 = 2 입니다.

• 시간 복잡도 O(n/2) , 소요시간 약 7초

방법 3 :

•  12(n)의 약수는 1, 2, 3, 4, 6, 12

• 1X12, 2X6, 3X4, 대칭으로 4X3, 6X2, 12X1 

• 따라서 12에 루트를 씌운 수 1, 2, 3, 까지만 반복

• 그리고 현재까지 구해진 약수 1, 2, 3을 이용

• n/1=12, n/2=6, n/3=4 을 통해 약수 구하기 

• 단 제곱수는 두번 약수에 더해지지 않도록 주의

• 예를 들면 9의 약수 1X9, 3X3, 9X1 에서 제곱수(3)

import time cnt = int(input('약수를 구할 횟수 입력:')) divs = [] for i in range(cnt): n = int(input('숫자 입력:')) d = [] s = time.time() for i in range(1, int(n**0.5)+1): if n%i == 0: d.append(i) if i!=n//i: d.append(n//i) divs.append(set(d)) print(n,'의 약수 : ', *d, '\n소요시간 : ', time.time()-s,'(sec)') print() if cnt>1: comdiv = set.intersection(*divs) print('공약수 : ', *comdiv) print('최대 공약수 : ', max(comdiv))

파이썬에서 '**' 은 제곱을 이므로, n의 0.5 승 즉, 루트를 의미합니다.

import math 구문을 통해 math.sqrt(n) 으로도 사용 가능합니다.

• 시간 복잡도 O(sqrt(n)) , 소요시간 약 0.001초

방법 1, 방법 2에 비해 약 13,000배 빠른 결과를 보입니다.

1억의 약수를 구하는데 sqrt(100,000,000) = 10,000 번의 반복만 수행한 결과입니다.

마지막으로 최대공약수를 구하는 방법은 python의 import math 후 math 모듈의 math.gcd(x, y) 를 통해 쉽게 구할 수 있습니다.

하지만, 위 코드에서 파이썬의 집합(set) 자료형을 통해 약수의 집합을 구성한 후, 각 집합의 교집합(intersection)을 통해 공약수를 찾는 방법을 사용하였습니다.

우리의 목적은 프로그래밍 공부이며, 코드의 구현이 아니기 때문입니다.

사용하기 쉬운 라이브러리나 내장함수만 사용해서는 실력이 늘지 않습니다.

감사합니다.