(알고공부 D-4)


# "1000 이하의 소수를 나열하기" 코드 이해하기


<코드>


# 1000 이하의 소수를 나열하기 (알고리즘 개선 2)

ptr = 0 # 이미 찾은 소수의 개수
prime = [None] * 500 # 소수를 저장하는 배열

prime[ptr] = 2 # 2는 소수
ptr += 1

prime[ptr] = 3 # 3은 소수
ptr += 1

for n in range(5, 1001, 2): # 홀수만을 대상으로 설정
 i = 1
 while prime[i] * prime[i] <= n:

if n % prime[i] == 0: # 나누어 떨어지므로 소수가 아님
 break # 반복 중단
i += 1


else: # 끝까지 나누어 떨어지지 않았다면

prime[ptr] = n # 소수로 배열에 등록
ptr += 1


for i in range(ptr): # 소수 출력
 print(prime[i])


(설명)


n의 순서쌍 p,q에서 p>=q일 때 p가 n으로 나누어떨어지는지 확인하면 q는 자동적으로 n으로 나누어떨어진다고 판단할 수 있다. 예시로 16은 순서쌍 (2,8), (4,4), (8,2)가 있는데 여기서 (2,8)과 (8,2)는 대칭구조이다. 우리는 n인 16이 2로 나누어떨어진다는걸 확인하면 저절로 8로도 나누어떨어진다는걸 순서쌍 (8,2)로 확인할 수 있다. 그러므로 p로 나누어떨어지는지 확인하면 되는데, 이 경우 대칭인 순서쌍의 경우는 제외한다. 즉 여기서는 (2,8), (4,4) 범위에서만 나눗셈을 수행한다. 즉 순서쌍 (sqrt(n), sqrt(n)) (* 16의 경우 (4,4)) 이하의 범위까지 p로 나눗셈을 시도하면 된다. 이걸 소수 판단에 응용하면, 어떠한 정수 n이 sqrt(n) 이하의 소수들로 나누어떨어지지 않는다면 소수라고 판단할 수 있다. 다시 말해 정수 n은 n의 제곱근 이하의 어떤 소수로도 나누어떨어지지 않을 때 소수이다.


이걸 응용한 것이 바로 해당 코드이다. 이 코드에서 우리가 고려해야 할 점이 있다. 5부터 1000까지의 홀수 중에서 소수인지 판단하기 위해서는 for문으로 반복해서 판단해줄 수 있다. 소수 판단은 판단하고자 하는 숫자 -1까지의 소수로 나누어떨어지는지 유무로 확인할 수 있다. 그렇다면 5 ~ 1000 사이 정수를 for문으로 소수인지 판단하고 소수가 나올 때마다 배열에 넣어준 다음 그 배열 원소들로 정수가 나뉘는지 확인해야 한다. 여기서 우리는 앞서 설명한 순서쌍 (sqrt(n), sqrt(n))을 사용할 수 있다.


코드를 보면 while문에서 i = prime[i] * prime[i] <= n: (소수의 곱 <= n)이다.

여기서 while prime[i] * prime[i] <= n: 반복문은 앞서 말했듯이 어떠한 정수 a가 sqrt(n) 이하의 소수들로 나누어떨어지지 않는다면 소수라고 판단할 수 있기 위함이다.


이에 대해 설명하기 위해 필자는 앞서 설명했던 순서쌍 (sqrt(n), sqrt(n))을 독특하게 이해해봤다. 앞서 어떠한 정수 n이 sqrt(n) 이하의 소수들로 나누어떨어지지 않는다면 소수라고 판단할 수 있다고 했다. 이 구조를 이해하기 위해 임의의 정수 77을 소수 판단한다고 생각해보자.

(* prime[1] = 3, prime[2] = 5, prime[3] = 7, prime[4] = 11)

77의 경우 prime[1], prime[2]로는 나누어떨어지지 않으나, prime[3]인 7에서 나누어떨어져 소수가 아니다. 필자는 77의 경우 sqrt(n)을 prime[3]으로 해석하였고, 이하의 소수로 prime[1], prime[2]가 추가로 있다고 생각했다. 즉 77이 소수인지 아닌지에 대해 판단하기 위해서는 prime 배열원소 1부터 3로 나누어떨어지는지 판단하는 것이다. 이는 앞서 16을 소수판단하기 위해서는 2, 4로만 나누어본다고 한 말과 일맥상통한다.

prime[i] * prime[i] <= n로 한 이유는 정수 n이 소수이려면 n 제곱근 이하의 어떤 소수로도 나누어떨어지지 않아야하기 때문이다. 원래는 prime[i] <= sqrt(n)으로 해야 하나 편의상 저렇게 한 것이다.



코드를 보면 소수 판단은 배열 인덱스 1인 3부터 시작하고, 소수가 생긴다면 배열에 등록하면서 1000까지 반복한다.

소수판단하는 과정과 소수로 판별된 정수를 배열에 등록하는 과정은 각주에 잘 설명되어 있으니 참조하면 된다.



일단... 졸면서 이해한 코드라서 제대로 이해 못한거같기도 하고.. 그냥 내 능지문제인거같아서 아침에 다시 차근차근 뜯어서 이해해봐야지

설명을 쓰긴 했지만 prime[i] * prime[i]로 해야하는 이유가 아직 딱 와닿지가 않음



# 내일 목표

- 이 문제 제대로 이해해보고 혼자서 짜보기

- 컴과 인강 2개 듣기

- 백준 3문제

- do it 2강 복습