E - ネットワークの巡回点検 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 466 点

問題文

高橋君は、N 台のサーバーからなるネットワークの点検を担当しています。各サーバーには 1 から N までの番号が付けられています。

高橋君は、以下の手順に従ってすべてのサーバーを点検します。

  1. 未点検のサーバーのうち番号が最小のものを s とする。サーバー s を点検し、ここから新たな巡回を開始する。手順 2 に進む。
  2. 現在いるサーバー（直前に点検したサーバー）の番号を k とする。
  • k = 1 の場合： 1 は素因数を持たないため、特別に扱う。番号が k より大きい未点検のサーバーが存在すれば、その中で番号が最小のサーバーに移動して点検し、手順 2 を繰り返す。存在しなければ、この巡回を終了し、手順 3 に進む。
  • k \geq 2 の場合： 番号が k より大きい未点検のサーバーのうち、番号と k が共通の素因数を少なくとも 1 つ持つ（すなわち、番号を m として \gcd(k, m) \geq 2 である）ものを考える。そのようなサーバーが存在すれば、その中で番号が最小のサーバーに移動して点検し、手順 2 を繰り返す。存在しなければ、この巡回を終了し、手順 3 に進む。
  1. 未点検のサーバーが残っていれば手順 1 に戻り、新たな巡回を開始する。すべてのサーバーを点検していれば終了する。

高橋君が巡回を開始した回数、すなわち手順 1 が実行された回数を求めてください。

制約

  • 1 \leq N \leq 5 \times 10^5
  • N は整数である。

入力

N
  • 1 行目には、サーバーの台数を表す整数 N が与えられる。

出力

高橋君が巡回を開始した回数を 1 行で出力せよ。

入力例 1

10

出力例 1

4

入力例 2

6

出力例 2

3

入力例 3

100

出力例 3

25

入力例 4

100000

出力例 4

9621

入力例 5

1

出力例 5

1

Score : 466 pts

Problem Statement

Takahashi is in charge of inspecting a network consisting of N servers. The servers are numbered from 1 to N.

Takahashi inspects all the servers according to the following procedure:

  1. Let s be the uninspected server with the smallest number. Inspect server s, and start a new patrol from here. Go to Step 2.
  2. Let k be the current server (the server inspected most recently).
  • If k = 1: Since 1 has no prime factors, it is treated as a special case. If there exists an uninspected server with a number greater than k, move to the one with the smallest number among them, inspect it, and repeat Step 2. If no such server exists, end this patrol and go to Step 3.
  • If k \geq 2: Consider the uninspected servers with numbers greater than k that share at least one prime factor with k (that is, letting the server's number be m, \gcd(k, m) \geq 2). If such servers exist, move to the one with the smallest number among them, inspect it, and repeat Step 2. If no such server exists, end this patrol and go to Step 3.
  1. If there are still uninspected servers, return to Step 1 and start a new patrol. If all servers have been inspected, terminate the process.

Find the number of times Takahashi started a patrol, which is the number of times Step 1 was executed.

Constraints

  • 1 \leq N \leq 5 \times 10^5
  • N is an integer.

Input

N
  • The first line contains an integer N representing the number of servers.

Output

Print the number of times Takahashi started a patrol in a single line.

Sample Input 1

10

Sample Output 1

4

Sample Input 2

6

Sample Output 2

3

Sample Input 3

100

Sample Output 3

25

Sample Input 4

100000

Sample Output 4

9621

Sample Input 5

1

Sample Output 5

1