[파이썬 알고리즘 문제풀이 입문] 코드 구현력 기르기 - 소수의 개수 (에라토스테네스 체)

*문제 본문은 강의 내용과 관련되어 있어 자세하게 적지 않았습니다.

 

 

 

문제

자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요.

 

 

 

풀이

• 내 풀이

import sys
input = sys.stdin.readline

N = int(input())
sosu = list()

def check_sosu(n):
    for i in range(2, n):
        if n%i == 0:
            return False

for j in range(2, N):
    if check_sosu(j) == False:
        continue
    else:
        sosu.append(j)

print(len(sosu))

 

• 답안 : Python

import sys
input = sys.stdin.readline

N = int(input())
sosu = [0] * (N+1)
count = 0

for i in range(2, N+1):
    if sosu[i] == 0:
        count += 1
        for j in range(i, N+1, i):
            sosu[j] = 1

print(count)

• 답안 : Kotlin (내가 바꿔본 것 / 정확X)

import java.io.*
import java.util.*

fun main(args: Array<String>) = with(BufferedReader(InputStreamReader(System.`in`))){
    var N = readLine().toInt()
    // .toMutableList() 해주지 않으면 읽기 전용 List를 반환하게 된다.
    var sosu = (1..N+1).map{0}.toMutableList()
    var count = 0

    for(i in 2 until N+1) {
        if(sosu[i] == 0) {
            count += 1
            for(j in i until N+1 step i) {
                sosu[j] = 1
            }
        }
    }

    print(count)
}

- 단순히 소수를 찾아서 개수를 출력하는 것에만 초점을 두고 코드를 짰는데, 답안을 보니 제일 빠른 방법으로 소수 개수를 구하는 방법이 있다는 것을 알게 되었고, 시간도 빠르면서 코드도 간단한 것을 보고 더 좋은 코드에 대해서 고민하는 노력을 해야겠다고 생각했다.

- 가장 빠른 방법으로 소수 개수를 구하는 방법을 '에라토스테네스 체' 라고 한다고 한다. (여기서 체는 '거르는 체')

 

[로직 설명]

- 인덱스가 N+1개만큼 있고, 0으로 초기화된 리스트를 선언해준다.

   (인덱스 번호로 접근하는데, 리스트 인덱스는 0부터 시작하기 때문에 +1을 해준다.)

- 만약 소수라면 해당 인덱스의 값은 0, 소수가 아니라면 1이 들어가게 된다.

- 해당 인덱스의 값이 0이라면(= 소수일 때) count를 1 증가시켜준다.

- 두번째 for문에서는 range()로 범위를 설정할 때, step을 이용해서 해당 인덱스의 배수들을 걸러내는 작업을 진행한다.