군대에서_코딩하기_알고리즘_7

오늘의 문제는, 자연수 N을 입력했을 때, 1부터 N까지 총 몇개의 소수가 있는지 파악하는 문제다. 물론 런타임 1초 제한이 있기 때문에, 이전글에 올린 메카니즘을 살짝 이용했다.
우선 코드는 다음과 같다.

#include<iostream>
#include<cmath>

using namespace std;

int main(){
    
    int N, i, j, num;
    
    cin >> N;
    int check = 0, res=0;
    
    if(N==2){
        res = 1;
    }
    else if(N==3||N==4){
        res = 2;
    }
    else{
        for(i=5; i<=N; i=i+2){
            //i가 5, 7, 9, 11 ... 짝수는 어차피 소수가 아니기 때문에
            //홀수만 취급
            num = (int)sqrt(i);
            //제곱근까지만 for문을 돌려도 소수를 판별할 수 있음.
            for(j=2; j<=num; j++){
                //
                if(i%j==0){
                check++;
                break;
            }
        } 
        }
        if(N%2==1){
            res = (N/2+1) - check;
        }
        else{
            res = (N/2) - check;
        }
        
    }
    
    cout<<res;
    
}

강의를 듣고 나서 안건데, 굳이 cmath 라이브러리를 추가해서 sqrt 함수를 쓰지 않았어도, 그냥

for(i = 2; i*i<N; i++) 

이런식으로 처리를 해줬어도, 똑같은 sqrt의 효과를 낼 수 있다..
그리고 음.. 강의에서는 안나왔지만, 나는 for을 최대한 적게 돌리기 위해서 짝수들은 일단 다 배제했다. 어차피 짝수들은 2로 나눠지기때문에, 소수가 아니므로 200000번 돌릴거 100000번만 돌리면 되지 않겠냐,,라는 마인드로 애초에 짝수는 배제하고 코들 짰다.
그래도 런타임 초과가 나지않고 100점 ㅎㅎ