[프로그래머스] 소수 찾기 (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를 반환

 

 

풀이)

 

#include <string>
#include <vector>
 
using namespace std;
 
int solution(int n) {
    
    // 1은 소수가 아니므로
    int answer = n - 1;
 
    // 에라토스테네스의 체
    // n + 1 크기의 배열 생성 (기본값은 true)
    vector<bool> eratos(n + 1, 1);
    
    // 1은 소수가 아니므로 2부터 시작
    // 효율을 위해서 i * i까지만 탐색해준다.
    for(int i = 2; i * i <= n; i++)
    {
        // 만약 i번이 소수라면 확인 작업을 한다.
        if(eratos[i])
        {
            // 자기 자신을 제외한 자신의 배수를 모두 false 처리 한다.
            // 이때 i*k (k < i) 까지는 이미 검사되었으므로 i * i 부터 시작.
            for(int j = i * i; j <= n; j += i)
            {
                // 소수가 아닌데 소수라고 되어있다면.
                if (eratos[j] == true)
                {
                    // false처리를 하고 answer를 하나 빼준다.
                    eratos[j] = false;
                    answer--;
                }
            }
        }
    }
    
    return answer;
}

---

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

프로그래머스