[프로그래머스/C++] Lv.1 소수 찾기

문제

문제

---

코드

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    vector<bool> prime(n+1, true);
    
    for(int i = 2; i<=n; i++)
    {
        if(prime[i])
        {
            for(int j = 2; j*i<=n;++j)
            {
                prime[j*i] = false;
            }
             answer++;
        }
       
    }
    return answer;
}

 

---

문제 해설

- 에라스토테네스의 채를 이용한다.
- vector<bool> prime(n+1, true) 를 만들어 모든 숫자가 소수라고 가정한다.
- 소수는 2부터 시작하기 때문에 for(int i = 2...)
- 소수인 경우에만 실행 prime[i]
- i의 배수를 찾고 소수가 아니기 때문에 false 처리
- 소수인 경우에만 answer++