소수 개수 세기

문제

자연수 N이 주어질 때, 1 이상 N 이하인 정수 중 소수의 개수 $\pi(N)$를 구하라. 소수는 1과 자기 자신으로만 나누어지는 2 이상의 자연수를 뜻한다.

입력

첫째 줄에 자연수 N이 주어진다.

• $1 \le N \le 10^8$

출력

1 이상 N 이하의 소수 개수 $\pi(N)$을 한 줄에 정수로 출력하라.

예제 입력 1

10

예제 출력 1

4

예제 입력 2

1000

예제 출력 2

168