朴素筛质数
import java.util.*;
public class Main {
static final int N = 1000010;
static int[] nums = new int[N];
static int[] primes = new int[N];
static int cnt = 0;
static boolean[] st = new boolean[N];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for (int i = 2; i <= n; i++) {
if (!st[i]) {
primes[cnt++] = i;
}
for (int j = i; j <= n; j += i) st[j] = true;
}
System.out.println(cnt);
}
}