말 그대로 10001번째 소수를 구하라!! 소수란 자연수 중 1과 자기자신으로만 나누어지는 수를 말합니다. 따지고 보면 결국 모든 자연수는 소수의 집합으로 이루어 지는데... 그 논리는 소인수분해에서 설명이 되지요. 참 이런걸 발견한 수학자들은 대단한 것 같습니다.
소수를 나열해 보면, 2 3 5 7 11 13... 이렇게 나가고 5번째 소수는 11이 되는 것 입니다. 그럼 10001번째 소수는 무엇일까요?? 만번째를 어떻게 구해... 너무나 오랜 시간이 걸리는거 아니냐... 우리에겐 컴퓨터가 있고 알고리즘이 있는데 무엇이 문제겠습니까?? ㅎㅎ
역시나 Test Case가 많이 들어오는 것을 기준으로 생각을 해보겠습니다.
(기준은 Test Case가 1000개, 목표 번째 소수는 최대 10001)
이렇게 큰 수까지 여러번 반복하려면, 어떻게 하는 것이 효과적일까요?? 맞습니다. 얼마전에 한 것처럼 특정 변수에 한번 결과를 저장하고 이를 계속 호출하는 방법이 있겠습니다. 그럼 전체적으로 아래의 단계로 해결해 보겠습니다.
- 첫번째 부터 10001번째 소수까지 우선 구해놓는다.
- Test Case가 주어질때마다 값을 호출해서 출력한다.
그럼 단계별로 구현해 볼까요??
1. 첫번째 부터 10001번째 소수까지 우선 구해놓기
모든 자연수는 소수들로 이루어져있다는 정의를 기반으로 구현을 해보겠습니다. 이 말은 원하는 숫자를 지속적으로 증가 시키면서... 기존에 구해졌는 작은 소수로 나눠진다면 이는 소수가 아니고, 나눠지지 않는다면 이는 소수가 될 것 입니다.
여기에 기존에 계속 반복해왔던 개념 1가지가 더 들어갑니다. 나누기를 할때 자신의 sqrt( )보다 큰 수는 연산할 필요가 없다!! 왜냐하면 이미 앞단에서 작은수의 나눗셈 몫으로 구해졌기 때문이다!!
이렇게 2가지를 구현한다면 아래의 코드로 대표됩니다.
def preCalc():
res = []
res.append(2)
cnt = 3;
while True:
chkPoint = math.sqrt(cnt)
addOk = True
for i in res:
if i > chkPoint: break
if cnt % i == 0:
addOk = False
break
if addOk: res.append(cnt)
if len(res) == 10001: break
cnt += 1
return res최초의 소수인 2는 강제적으로 추가했으며, 자연수 3부터 순차적으로 증가시키면서 기존의 소수로 나눠지면 다음 자연수로 넘어가고... 10001번째 소수가 구해졌다면 종료하도록 했습니다.
2. Test Case가 주어질때마다 값을 호출해서 출력
이부분은 간단합니다. 그냥 입력받은 숫자로 배열내 값을 찾아서 출력만 해주면 되니까요... 그럼 전체 코드는 아래와 같습니다.
# Problem 7
import math
def preCalc():
res = []
res.append(2)
cnt = 3;
while True:
chkPoint = math.sqrt(cnt)
addOk = True
for i in res:
if i > chkPoint: break
if cnt % i == 0:
addOk = False
break
if addOk: res.append(cnt)
if len(res) == 10001: break
cnt += 1
return res
if __name__ == '__main__':
primeNo = preCalc()
tc = int(input())
for i in range(tc):
target = int(input())
print(primeNo[target-1])이렇게 Problem 7도 통과 했습니다.
-Ayotera Lab-
댓글