알고리즘 문제를 풀다가 채점결과에서 효율성이 0점이 나왔다 ㅋㅋ..

확실히 문제를 풀면서 '아 이건 효율성이 좀 많이 떨어질거 같은데..' 가 딱 들어맞았다.

효율성 문제를 찾다가 '에라스토테네스의 체' 라는 소수 판별 알고리즘을 발견했다. 

 위와 같이 '에라스토테네스의 체' 알고리즘을 쓸 경우는 시간 복잡도가 O(N^(1/2)) 이다.

코드 설명

1 . vector<bool> 을 입력받은 n만큼 범위를 지정하고 true로 초기화합니다.

2. for문은 2부터 n+1까지 1씩 증가합니다. (1은 소수에 미포함이기 때문에 2부터 증가)

3. tmp[i]가 true일 경우 for문 하나가 돌아가는데  가장 먼저 2의 배수를 가진 tmp[i]는 모두 false가 됩니다. 

     (2 자신은 제외, answer++)

4. 다음으론 3의 배수가 전부 false 처리됩니다. (이 실행 이후 tmp[i]는 전부 소수만 남게 됨)

5. tmp[i] == true 라는 건 소수를 의미하게 되고 if문에 걸릴때마다 answer++을 하게되어 소수의 갯수를 찾게 됩니다.