소수 찾기

🔗 문제 링크

https://programmers.co.kr/learn/courses/30/lessons/12921

❔ 문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

⚠️ 제한사항

• 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
  (1은 소수가 아닙니다.)

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

---

💡 풀이 (언어 : Python & Java)

에라토스테네스의 체를 이용한 알고리즘으로 풀었다. 해당 소수의 배수들을 소수가 아니라고 배열에 체킹해줘서 소수인지 확인하는 연산의 횟수를 대폭 줄이는 알고리즘이다.

Python

def solution(n):
    count = 0
    # 범위를 n+1 까지 해주어야 함 
    # (0번째 인덱스 무시하고 1번째부터 숫자 1이라고 가정)
    lis = [False for i in range(n+1)]
    # 리스트 생성을 n까지 하면 for문 range(1, n)이 되어 
    # 에라토스테네스 체(배수 삭제) 사용 어려움
    # 소수는 2부터 n까지(인덱스는 +1 해야 맞음) 세기
    for i in range(2, n+1):
        # false일 경우에만 소수 카운트
        if lis[i] == False:
            count += 1
        # 에라토스테네스의 체로 해당 턴 숫자의 배수들(인덱스)은 true로 
        # 다음 루프에서 카운트 안되고 지나가게 함
        # i씩 더해줌 = i의 배수 
        for j in range(i*2, n+1, i):
            lis[j] = True
            
    return count

Java

class Solution {
    public int solution(int n) {
        int count = 0;
        // 소수의 배수들을 소수가 아닌 수로 기록하기 위한 배열
        boolean[] isNotPrime = new boolean[n+1];
        // 0과 1은 소수가 아니므로 true
        isNotPrime[0] = true; isNotPrime[1] = true;
        // 약수의 대칭 성질로 루트 n까지 반복
        for (int i = 2; i <= Math.sqrt(n); i++) {
            // 소수가 맞으면 그 소수의 배수들을 n 이하까지 소수가 아니라고 배열에 기록
            if (!isNotPrime[i]) {
                for (int j = 2*i; j < n+1; j += i)
                    isNotPrime[j] = true;
            }
        }
        // 소수 여부 배열을 조회해 소수 개수를 카운트
        for (boolean c : isNotPrime) {
            if (!c)
                count++;
        }
        return count;
    }
}