소수 구하는 방법

안녕하세요 Dibrary입니다.

알고리즘을 풀다보면 꼭 마주하는 문제들이 몇 개 있습니다. 소수, 최소공배수, 최대공약수 등등... 중고등학교때는 그저 술술 풀었지만, 코딩으로 하자니 막상 숨이 턱. 막히는 그런 개념들이죠.

그 중에 이번에는 '소수'를 구하는 코드를 정리해보겠습니다.

 

대표적인 문제로는 아래 문제가 있습니다. 대놓고 소수 구하기 라고 하죠 .

1929번: 소수 구하기

 

---

우선, 소수란 '자기 자신과 1만을 약수로 갖는 수' 입니다.

예를 들어보죠,
2는 1과 2만을 약수로 가집니다. 소수죠.
3도 1과 3만을 약수로 가집니다. 소수입니다.
4는 1과 2, 4 이렇게 1과 4외에 다른 숫자가 들어있으므로 소수가 아닙니다.
7은 1과 7만을 약수로 가지므로 소수입니다.

 

정말 개념은 간단하죠. 중고등학교때 배운 것으로 우리는 기본적으로 아래의 과정을 거쳐서 소수인지를 판정합니다.

1. 나눗셈이 될까? n으로 나눠서 m을 구할 수 있네, 그럼 약수에 n과 m이 있으므로 소수라고 할 수 없다.
2. n과 m의 곱셈으로 구할 수 있네, 그럼 약수에 n과 m 이 있으므로 소수라고 할 수 없다.

그렇지 않나요? 저는 제가 소수 판정을 어떻게 하나 곰곰히 생각 해 보니 위와 같은 사고를 하고 있었습니다.

 

---

그럼, 문제로 가보죠.

그냥 주어진 범위내의 소수를 구하는게 끝입니다.

 

결국, '소수를 어떻게 구하느냐'가 관건이죠. 주어진 수의 범위는 100만개 까지니까요.

정답 코드는 아래와 같습니다.

근데, 알고리즘은 답이 중요한게 아니라 '왜 그렇게 해서 구할 수 있느냐'가 핵심이죠.

코드에서 isPrime이라는 함수가 곧 소수인지 판정하는 거름막 역할을 합니다.

잘 보면 isPrime 함수 내의 for문이 좀 이상하죠? int(num**0.5) + 1 이 부분이 좀 의아할 수 있습니다.

이렇게 범주를 구한데는 2가지 이유가 있습니다.

1. for문을 끝까지 가게 하지 않아도 되므로 소요 시간을 줄일 수 있습니다.
2. 수학적으로 해당 범위까지만 계산해도 된다.

1은 당연히 시간측면에서 이익이 되니까 그런데, 굳이 왜 int(num**0.5) + 1값이냐~. 그 이유는 2번에 있습니다.

 

100이라는 숫자를 예로 들어보겠습니다.

100은 10*10이죠, 즉, 10이라는 약수를 가지고 있습니다.

잘 보면 10*10을 기준으로 반드시 한쪽의 값이 10보다 커지지 않는다는 것을 알 수 있습니다.

절반에 해당되는 숫자의 곱 이후부터는 다시 한쪽의 값이 작아지므로 사실상 이미 구했던 약수가 됩니다.

10*10에 도달하기 전에, 50*2는 10*10 이후에 2*50으로 다시 나타났고,
25*4는 10*10 이후에 4*25로 다시 나타난 것을 볼 수 있습니다.

따라서, 약수를 구할 때는 (절반값*절반값)까지만 구하면 사실상 약수를 다 구한 셈이 됩니다.

아 근데 왜 1을 더하냐구요? int(num**0.5)의 값 결과 가 '버림'처리가 되기 때문입니다.

45를 예로 들었는데, 루트씌운 후, int로 변경하니 0.7이라는 값이 잘립니다. 근데, 사실 0.7도 고려를 해 줘야 하죠. 

그래서 그냥 +1을 더한 겁니다. 사실상 버림의 범주는 0부터 0.99까지일 테니까요. 

 

 

그래서 위 isPrime 함수 코드는 나누어 떨어지는 수가 있는지 보고, 

하나라도 나눠 떨어지면 약수가 1과 자기자신만 있는게 아니라고 판단해 return False를 내보냅니다.

 

한번 이해를 잘 해 두면 그 다음부터 구현은 굉장히 쉽게 하실 수 있습니다.

이걸 for문에서 num까지 계산해도 결과는 같게 나옵니다. 다만, 시간초과에 걸릴 확률이 더 높을 뿐이죠.