public class PrimeSieve {
    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]);
        boolean[] primo = new boolean[n + 1];

        // Inizializza tutti i numeri come primi
        for (int i = 2; i <= n; i++) {
            primo[i] = true;
        }

        // Implementa il Crivello di Eratostene
        for (int i = 2; i * i <= n; i++) {
            if (primo[i]) {
                for (int j = i * i; j <= n; j += i) {
                    primo[j] = false;
                }
            }
        }

        // conto tutti i numeri primi trovati
        int count = 0;
        for (int i = 2; i <= n; i++) {
            if (primo[i]) {
                count++;
            }
        }

        System.out.println(count + " numeri primi trovati fino a " + n);
    }
}