[정수론] 약수 구하기, 소수 판정하기

목표

약수가 무엇인지 알고, 빠른 시간 안에 모든 약수를 구하는 Python 코드를 설계해본다.

소수가 무엇인지 알고, 빠른 시간 안에 소수를 판정하는 Python 코드를 설계해본다.

약수 구하기

약수란?

어떤 자연수 N이 주어졌을 때, 그 자연수 N이 또 다른 자연수 K의 배수로 곱해지면 K가 N의 약수라고 부른다.

즉, `N = K * A` (단, N, K, A는 자연수) 라는 식이 성립되면 K가 N의 약수인 것이다. 

K가 N의 약수인지 판단하는 방법은 아주 쉽다. N을 K로 나누었을 때 나누어 떨어지는지 확인하면 된다.

if n % k == 0:
	print('약수')
else:
	print('약수 아님')

그렇다면, 어떤 자연수 N이 주어졌을 때 N의 모든 약수를 알아내는 방법은 무엇일까?

1부터 N까지 i에 대입하며 N을 i로 나누어 보는 것이다. 코드를 살펴보면...

for i in range(1, n + 1):
	if n % i == 0:
    		print(i)

위 코드는 문제가 없지만, 만약 N의 크기가 무척 커진다면? 만약 N이 10억이라면 10억번 가량의 연산을 해야할 것이다.

이 문제를 해결하기 위해 약수의 특징을 알아보자.

다음 그림은 48의 약수를 나열한 뒤, 서로 곱했을 때 48이 나오는 숫자끼리 묶은 그림이다.

그림에서도 알 수 있듯이, 약수는 (작은 수)와 (큰 수)의 곱으로 이루어져있다. (작은 수)와 (큰 수)는 각각 `\sqrt{n}`보다 작고, `\sqrt{n}`보다 크다. (`\sqrt{n} * \sqrt{n} = n` 이기 때문)

이것을 활용해 1부터 n까지 모든 수가 N의 약수인지 확인하지 않고 1부터 `\sqrt{n}`까지의 수가 N의 약수인지 확인하면 된다.

import math

for i in range(1, int(math.sqrt(n)) + 1):
	if n % i == 0:
    		if i != n // i:
    			print(i, n // i)
            	else:
            		print(i)

단, 위 코드는 완전 제곱수의 경우 `\sqrt{n}`을 두 번 출력하게 된다. 그 처리만 해주면 비로소 "약수 구하기" 코드가 된다.

소수 판정하기

소수란?

소수란, 1보다 큰 자연수 중 1과 자기 자신만을 약수로 갖는 수 입니다.

 

어떤 수가 소수인지는 어떻게 판단할 수 있을까요? N을 1부터 N까지의 수로 나누어 본 뒤, 나누어 떨어지는 수가 정확히 2개이면 소수라고 할 수 있습니다.

n = int(input())
cnt = 0
for i in range(1, n + 1):
    if n % i == 0:
        cnt += 1

if cnt == 2:
    print("소수입니다.")
else:
    print("소수가 아니네요.")

모든 약수를 구하는 코드와 마찬가지로 `O(n)`의 시간복잡도를 가집니다. 모든 약수를 구할 때와 비슷한 방식으로 `O(n)`의 시간 복잡도를 `O(\sqrt{n})`까지 낮출 수 있습니다.

 

현재 알고리즘은 다음과 같습니다.

1. 우선, 숫자 N의 약수를 구한다.
2. 약수의 개수가 2라면 소수이고 2보다 크다면 소수가 아니다.

이걸 최적화 하면

1. 숫자 N의 약수를 구하는데, 약수를 구할 때 1부터 `\sqrt{n}`까지만 확인한다.
2. 그렇게 구한 약수의 개수가 1이라면 소수이고 1보다 크다면 소수가 아니다.

위 방식으로 최적화한 코드는 다음과 같습니다.

import math

n = int(input())
cnt = 0
for i in range(1, int(math.sqrt(n)) + 1):
    if n % i == 0:
        cnt += 1

if cnt == 1:
    print("소수입니다.")
else:
    print("소수가 아니네요.")