[Programmers] 12921. 소수 찾기

// [1]
int arr[1000000];
int solution(int n) {
    int answer = 0;
    for (int i = 2; i <= n; i++) {
        arr[i] = i;
    }
    for (int i = 2; i <= n; i++)
    {
        if (arr[i] == 0)
            continue;
            /*
            소수의 배수들은 무조건 소수가 아니다.
            ex) 3일 경우
            3의 배수 6,9,12,15 등등
            (= 소수 x 2,3,4,5 등등 )
            그렇기 때문에
            j에는 소수인 i의 2배값을 넣어주고
            j += i 를 해줌으로써 배수들을 다 제거해준다.
            */
        for (int j = i + i; j <= n; j += i)
            arr[j] = 0;
    }
    for (int i = 2; i <= n; i++)
        if (arr[i] != 0)
            answer++;
    return answer;
}

// [2]
int solution(int n) {
    int answer = 0;
    /*
    num(n)으로 해도 되지만
    n=10일때
    num[9]가 10값을 뜻하게 되므로 
    num(n+1)로 해준다.
    대신 이러면 num[0]은 사용하지 않는다.
    */
    vector<int> num(n+1);
    
    for(int i=2; i <=n ; i++) {
        if(num[i]==1) {
            continue;
        }
        else {
            answer++;
            for(int j=i*2; j < num.size(); j+=i) {
                num[j]=1;
            }
        }
    }
    return answer;
}