import math # 平方根の計算 sqrt にのみ利用

def tamesiwari(n):
    yakusuu=0
    for i in range(1,n+1):
        if(n%i==0):
           yakusuu=yakusuu+1
    return yakusuu

def furui(tlist, slist): # tlist:探索リスト, slist:素数リスト
    # 探索リストの先頭の数を素数リストに移動
    s=tlist.pop(0)
    print(s)
    slist.append(s)
    print(slist)
    # 探索リストのふるい落とし処理
    i=0
    for val in tlist:
        if(val%s==0):
            del tlist[i]
        i+=1
    print(tlist)
    # 探索リストの先頭値が数列の最大値の平方根に達するまで行う
    x=max(tlist)
    print(tlist[0], math.sqrt(x))
    if tlist[0] > math.sqrt(x):
        return tlist, slist
    # ふるい落とし処理の再帰呼び出し
    return furui(tlist, slist)

# エラトステネスの篩
def eratosthenes(x):

    # step 1
    tansakulist=[]
    tansakulist=list(range(2,x+1))
    print(tansakulist)

    # step2,3
    sosuulist=[]
    tansakulist, sosuulist = furui(tansakulist, sosuulist)

    # step4
    sosuulist.extend(tansakulist)

    return sosuulist

#n=
#for p in range(n,n+10):
#    if (tamesiwari(p)==2): # 試し割りの結果、約数の数量が2なら素数
#        print (p)

n = 26640483611824783825980077284251126959643154875431494492573037148561576194154184967684133407808241519378364083601700869966787931424796373816830749899282834223587532058268929912670892070676298193701529146795024207954976461139721153243891278235345376333179594026610249677526069249327326349120860403474817583705917900485139065225650861288050992982630527478054745857005054591705621770886268621387816467159000699502254793894406982648327242800670612163012899640036439024993503089700282998008573059031154601152122932316556268855145599004150582164688388061834521863831053705155025891664155040237275594781567983128101356634010

print(eratosthenes(n))