[연습문제] 소수 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/12921?language=python3

프로그래머스

---

문제 설명
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

---

제한 조건

• n은 2이상 1000000이하의 자연수입니다.

---

입출력 예

n	result
10	4
5	3

---

입출력 예 설명
입출력 예 #1

• 1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2

• 1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

---

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 문제입니다.

 

사실 코딩테스트에서는 잘 보는 유형은 아닌데, 준비 과정에서는 여러 번 보는 소수 찾기 문제입니다.

유명한 방법이 있죠? 에라토스테네스의 체 방법이 가장 빠른 시간 내에 소수의 개수를 구할 수 있습니다.

 

이번에는 자바와 파이썬으로 에라토스테네스의 체를 구현해보겠습니다.

 

1. 자바

import java.util.*;

class Solution {
    public int solution(int n) {
        // 소수를 판별하는 sieve 배열을 생성합니다.
        boolean[] sieve = new boolean[n + 1];
        // sieve 배열을 true로 초기화합니다.
        Arrays.fill(sieve, true);
        // 0과 1은 소수가 아닙니다.
        sieve[0] = sieve[1] = false;
        
        // 2부터 √n까지 소수 판별을 진행합니다.
        for (int i = 2; i * i <= n; i++) {
            // i가 소수일 경우
            if (sieve[i]) {
                // i의 배열은 소수가 될 수 없습니다.
                for (int j = i * i; j <= n; j += i) {
                    sieve[j] = false;
                }
            }
        }
        
        // 소수인 값들이 몇 개인지 셉니다.
        int answer = 0;
        for (boolean isPrime: sieve) {
            if (isPrime)
                answer++;
        }
        return answer;
    }
}

 

Arrays를 임포트한 이유는 Arrays.fill을 사용하기 위해서입니다.

boolean 배열의 기본값이 true면 좋겠는데, 아쉽게도 false이므로 이 값들은 전부 true로 바꿔줘야 하기 때문이죠.

물론 fill을 사용하실 필요는 없고, 반복문으로 하셔도 동일합니다.

2. 파이썬

def solution(n): 
    # 0부터 n까지 True로 초기화된 배열을 생성합니다.
    sieve = [True] * (n + 1)
    # 0과 1은 소수가 아닙니다.
    sieve[0] = sieve[1] = False
    
    # 2부터 √n까지의 값에 대해 소수 판별을 진행합니다.
    for i in range(2, int(n ** 0.5) + 1):
        # 해당 숫자가 소수(True)일 때
        if sieve[i]:
            # i의 배수들은 소수가 아닙니다.
            for j in range(i * i, n + 1, i):
                sieve[j] = False
    
    # True의 개수를 더합니다.
    return sum(sieve)

 

연습문제이니만큼 원래 의도는 반복문으로 하나하나 값이 소수인지 체크하라는 뜻이었을지도 모르겠네요.

하지만 에라토스테네스의 체라는 확실한 방법은 기억해두시는 게 좋습니다.