#!/usr/bin/python3
#
# A program that takes an integer N > 0 as a command-line parameter,
# and prints the values of \pi(i) for all i <= N, where \pi(k) is the
# number of prime numbers between 1 and k
#
import sys

def pi(n):
    # we implement the sieve of Eratosthenes
    #
    S = [True]*(n + 1)
    S[0] = False
    S[1] = False
    p = 2
    while p * p <= n:
        if S[p]:
            i = p * p
            while i <= n:
                S[i] = False
                i = i + p
        p = p + 1

    count = 0
    i = 1
    while i <= n:
        if S[i]:
            count = count + 1
        print (i, count)
        i = i + 1

try:
    pi(int(sys.argv[1]))
except:
    print('usage:', sys.argv[0], '<n>')