약수와 소수(with 코드)

기초 수학이라 쉬울줄 알았는데 생각보다 파고들 점들이 많았으므로 따로 카테고리를 만들어 정리하게 되었다.

약수(Divisor)

어떤 수를 나누어 떨어지게 하는 수이다.

파이썬으로 약수 구하기

방법 1. 가장 단순하게 약수를 구하는 방법

이 경우, O(N)의 시간복잡도를 가지게 된다.

 

inputNum=int(input('정수 입력: '))

print('{}의 약수는'.format(inputNum))
for num in range(1, inputNum+1):
    if inputNum%num==0:
        print(num)
print('가 있습니다.')

 

방법 2. 해당 수의 반까지만 반복문을 진행하여 약수를 구하는 방법

예를 들어, 10의 약수는 {1, 2, 5, 10} 이다. 10을 반으로 나눈것보다 초과된 값은 절대로 약수가 될 수 없다. 이런점을 이용해 소스코드에 반으로 나눈값까지 계산하고 자신의 값을 추가하는 코드를 짤 수 있다.

1번 방법보다는 빠르지만 그래도 O(N)의 시간복잡도를 가지게 된다.

 

inputNum=int(input('정수 입력: '))

print('{}의 약수는'.format(inputNum))
for num in range(1, inputNum//2+1): # //는 몫만 가져오는 파이썬 연산자
    if inputNum%num==0: # if에는 괄호를 써도되고 안써도 된다.
        print(num)
print(inputNum)
print('가 있습니다.')

 

방법 3. N의 약수를 구할 때는, 1부터 N의 제곱근 까지의 수만 0으로 나누어 떨어지는지 확인하면 된다는 점을 이용한 방법

 

예를 들어, 100의 약수는 {1, 2, 4, 5, 10, 20, 50, 100}이다. 100의 제곱근은 10이다. 위 그림과 같이 100의 제곱근까지 구한 약수로 나머지 약수들을 구할 수 있다는 것을 알 수 있다.

이 경우, 시간복잡도가 O(√N)이 되어 위의 다른 방법들보다 빠르게 답을 구할  수 있게된다.

 

import math

inputNum=int(input('정수 입력: '))

print('{}의 약수는'.format(inputNum))
for num in range(1, int(math.sqrt(inputNum))+1): #파이썬 형변환은 int()같이 한다.
    if inputNum%num==0:
        print(num)
        if num!=inputNum//num:
            print(inputNum//num)
print('가 있습니다.')

#정렬은 따로 해주기

 

소수(Prime Number)

약수가 1과 자기 자신뿐인 수를 말한다. (1은 제외)

소수의 반대는 합성수이다.

파이썬으로 소수 구하기

소수도 결국 약수를 구하는 과정에서 판별이 난다. 그래서 위 약수구하기를 참고하여 가장 시간복잡도가 큰 첫번째 방법(O(N))과 가장 시간복잡도가 작은 세번째 방법(O(√N))을 이용해서 구해보자.

 

방법 1. 가장 단순하게 약수를 구하는 방법

 

inputNum=int(input('정수 입력: '))

for num in range(2, inputNum):
    sosu = True # 소수임을 판별하기 위한 플래그
    if inputNum%num==0: # 2~inputNum 사이에 약수가 하나라도 찾아지면 소수가 아님
        sosu = False
        break # 소수가 아니므로 반복 종료

if sosu==True:
    print('{}은/는 소수가 맞습니다'.format(inputNum))
else:
    print('{}은/는 소수가 아닙니다'.format(inputNum))

#삼항연산자를 이용해본 버전
#print('{}는 소수가 {}니다'.format(inputNum, '맞습'if sosu else '아닙'))

 

방법 2. N의 약수를 구할 때는, 1부터 N의 제곱근 까지의 수만 0으로 나누어 떨어지는지 확인하면 된다는 점을 이용한 방법

 

import math

inputNum=int(input('정수 입력: '))

for num in range(2, int(math.sqrt(inputNum))+1): # inputNum의 제곱근을 정수화 시켜준 후 + 1
    sosu = True # 소수임을 판별하기 위한 플래그
    if inputNum%num==0: # 약수가 하나라도 찾아지면 소수가 아님
        sosu = False
        break # 소수가 아니므로 반복 종료

if sosu==True:
    print('{}은/는 소수가 맞습니다'.format(inputNum))
else:
    print('{}은/는 소수가 아닙니다'.format(inputNum))

 

에라스토테네스의 체

만약 여러 개의 수에 대하여 소수 판별을 해줘야하는 상황일 때 사용하는 방식이다.

작동방식은

1. 2 ~ N까지의 범위가 담긴 배열을 만든다.

2. 해당 배열 내의 가장 작은 수 i 부터 시작하여, i의 배수들을 해당 배열에서 지워준다. (i자체는 지우지 않는다.)

3. 주어진 범위 내에서 i의 배수가 모두 지워지면 i 다음으로 작은 수의 배수를 같은 방식으로 배열에서 지워준다.

4. 더 이상 반복할 수 없을 때까지 2, 3번의 과정을 반복해준다.

숫자 n이 주어졌을 때 그 미만의 소수를 찾는데 최적화된 방식이다. 

 

import math

inputNum=int(input('정수 입력: '))

# 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
sosu = [True] * inputNum
sosu[0]=False # 0은 소수가 아니다.
sosu[1]=False # 1은 소수가 아니다.

for i in range(2, int(math.sqrt(inputNum))+1):
    if sosu[i] == True:           # i가 소수인 경우
        for j in range(i+i, inputNum, i): # i이후의 i의 배수들을 False 판정
            sosu[j] = False

# 소수 목록 산출
for i in range(len(sosu)):
    if sosu[i] == True:
        print(i)

처음에 False로 설정해둔다면 sqrt(inputNum)까지만 해주면 된다.