[Programmers - lv01] 소수 찾기 (cpp / python)

소수 찾기

코딩테스트 연습 - 소수 찾기

 

문제 설명

에라토스테네스의 체를 이용하여 소수를 찾는 문제

문제 풀이

*소스코드 : C++ *

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    vector<bool> tmp(n+1, true);

    for (int i=2; i<n+1; i++) {
        if (tmp[i] == true) {
            for (int j=2; i*j<n+1; j++) tmp[i*j] = false;
            answer++;
        }
    }

    return answer;
}

소스코드 : Python

def solution(n):
    answer = 0
    check = [False] * (n+1)
    check[0] = check[1] = True

    for i in range(2,n+1):
        if check[i] == False:
            for j in range(i*i, n+1, i):
                check[j] = True
            answer+=1

    return answer