[프로그래머스/C++ 문제 풀이] Lv. 1 - 소수 찾기

문제 설명

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

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

제한사항

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

입출력 예

 

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

 

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

---

문제 풀이

이번 문제는 일정 범위 내의 소수를 판별하는 문제입니다.

 

소수는1과 자기 자신만을 약수로 가지는 수이기에 저는 소수를 판별하기 위해 2부터 N까지 자기 자신을 제외한 배수들을 체크하고, 체크가 되지 않은 수(소수)를 세어 문제를 해결하였습니다.

 

기본적으로 "에라토스테네스의 체" 알고리즘을 알고 있다면 쉽게 풀 수 있는 문제이지만, 모르는 경우 시간 초과가 되기 쉬운 문제라고 생각합니다.

 

https://apth1023.tistory.com/73

[Algorithm] 에라토스테네스의 체 (소수 판별)

정답 코드

// 소수가 아닌 수를 체크하기 위한 배열
bool arr[1000002];

using namespace std;

int solution(int n) {
    int answer = 0;

    // 2부터 n까지의 수를 순회합니다.
    for (int i = 2; i <= n; i++)
    {   
        // 자기 자신을 제외한 배수들을 체크해줍니다.
        for (int j = i * 2; j <= n; j += i)
        {
            // 이미 체크된 수라면 넘어갑니다.
            if (arr[j] == 1) continue;

            // 체크된 수가 아니라면 체크해주도록 합니다.
            arr[j] = 1;
        }
    }

    // 소수가 아닌 수를 전부 체크했으므로 소수가 몇 개 존재하는지 체크합니다.
    for (int i = 2; i <= n; i++)
    {
        if (arr[i] == 0)
        {
            answer++;
        }

    }

    return answer;
}