소수(Prime Number)판단모듈(1)
소수(Prime Number)의 정의는 1과 자기자신을 약수로 가지는 수로 정의한다. 단, 1은 소수가 아니다.
위의 정의로 파이썬으로 소수 판단모듈을 구현해보면 아래와 같다.
예로 7은 1,7 만을 약수로 가짐으로 소수이다. 코드상에서 "소수판단: True" 로 결과 반환한다.
def prime_number(x):
# 소수정의에서 1은 제외임으로 2부터 x까지 모든 숫자를 시도한다.
for i in range(2, x+1):
#입력한 수가 2~자기자신으로 나누어 떨어지면 소수가 아니다.
if x % i == 0:
return False # 소수아니다.
return True # 소수가 맞다.
x=11
print('소수판단:{}' .format(prime_number(x)))
#결과:
#소수판단:True
소수(Prime Number)판단모듈(2)
위 1번 방법은 설정 범위내 전 숫자를 테스트함으로 판단시간이 오래 걸림으로 시간복잡도가 우려된다면
아래 판단모듈 (2) 사용을 고려해 보자.
예를 들어 6의 약수는 1,3,6 여서 소수가 아니지만 아래 모듈의 소수인지 판단 과정은 sqrt(6) = 2.44의 정수2까지 시도하여
6%2 == 0 으로 소수가 아님으로 False를 반환한다.
import math
def prime_number(x):# 소수정의에서 1은 제외임으로 2부터 x의 제곱근까지 시도함으로 입력수 제곱근의 정수 수준으로 반복이 준다.
for i in range(2, int(math.sqrt(x)) + 1):
if x % i == 0:
return False # 소수아니다.
return True # 소수가 맞다.
# 소수인지 테스트
for i in range(2,6+1):
print('Test Number:{}, 소수판단:{}' .format(i,prime_number(x=i)))
# 결과
#Test Number:2, 소수판단:True
#Test Number:3, 소수판단:True
#Test Number:4, 소수판단:False
#Test Number:5, 소수판단:True
#Test Number:6, 소수판단:False
약수(Divisior) 구하기 모듈(1)
약수(divisor)를 구하는 기본 알고리즘은 구간 1~ number+1까지 전체 range구간을 탐색하여 나머지가 0되는
for 문 인덱스를 추출하면 약수를 찾을 수 있으나, 코드테스트에서 전체구간을 탐색하다보니 시간복잡도 에러가 발생한다.
def divisor(number):
divisors = []
# range 구간은 1 부터 시작되도록 설정함.
# 마치는 range 구간도 number +1 까지로 1씩 뒤로 밀음.
for j in range(1,number+1):
# 입력받은 number에 j 인덱스 나눠 나머지가 0이면 리스트에 j 저장
if number % j == 0 :
divisors.append(j)
return divisors
result_divisor = sorted(divisor(number=20))
print(f'result divisor:{result_divisor}')
# >>> result divisor:[1, 2, 4, 5, 10, 20]약수(Divisior) 구하기 모듈(2): 시간복잡도 개선
range범위내 전 구간을 탐색하는대신 1 부터 number의 제곱근까지 구간을 탐색하여 약수를 구해 시간복잡도를 개선해 보자. range범위가 1~sqrt(number)구간으로 기존 대비 절반정도 계산량이 줄어든다. 따라서 시간복잡도 개선된 알고리즘을 활용하는게 코드테스트에서 중요 할 것 같다.
def divisor(number):
divisors = []
# range 구간은 1 부터 시작되도록 설정함.
# 마치는 range 구간은 제곱근까지 설정하면
# 전체구간을 탐색하는 대신 계산시간을 줄일 수 있음.
for j in range(1,int(number**0.5)+1):
# 입력받은 number에 j 인덱스 나눠 나머지가 0 이면 리스트에 j 저장
if number % j == 0 :
divisors.append(j)
# 위 if문 만족시 number// j 인덱스의 몫이 j와 같이 않다면 number//j 저장
if j != number// j:
divisors.append(number//j)
return divisors
result_divisor = sorted(divisor(number=18))
print(f'result divisor:{result_divisor}')
# >>> result divisor:[1, 2, 4, 5, 10, 20]