Programmers / 소수 찾기 / C++ - 에라토스테네스의 체

 

*문제 출처는 프로그래머스에 있습니다.

문제 제목: 소수 찾기

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/12921

프로그래머스

 

---

나의 풀이

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    vector<bool> arr(n+1,true); // 에라뭐시리 체 가능?
    arr[0] = false;
    arr[1] = false;
    for (int i = 2; i*i <= n; i++){
        if (arr[i] == false){
            continue;
        }
        else{
            for (int j = i * i; j <= n; j += i){ // i 의 배수들은 안된다
                arr[j] = false;
            }
            
        }
    }
    for(int i = 0; i < n+1; i++){
        if (arr[i] == true){
            answer += 1;    
        }
        
    }
    return answer;
}

 

범위 잘 기억하기 까먹으면 큰일난다.