def eratosthenes2(n):
    multiples = set()
    k=0
    for i in range(2, n+1):
        if i not in multiples:
            print(i), k,
            k+=1
            multiples.update(range(i*i, n+1, i))
 
eratosthenes2(10000)