# 先前那个错了啦，我是傻逼

import strutils, strformat

from math import sqrt, floor

var
    n = parseInt(readLine(stdin)) # 要求质数的范围上限
    numbers: seq[Natural] = @[]   # 剩余未判断素性的数字
    primes: seq[Natural] = @[]    # 质数们

for i in 2..n:
    numbers.add(i) # 初始化

while len(numbers) > 0:
    var
        p = numbers[0] # 最小的质数
        newNumbers: seq[Natural] = @[]

    primes.add(p) # 比自己小的都已经删掉或者进质数列表了，自己没被筛掉就是质数

    if p * p > n:
        break # 自己乘以自己都已经比上限的平方大了，那么自己啥也筛不到了，都被前面的因数筛完了

    for i, v in numbers:
        if not (v / p == floor(v / p)): # 不能被用来筛的质数整除，所以不知道是不是质数
            newNumbers.add(v) # 接着筛
        # 否则就淘汰，下一次不用筛了（这好像是一种优化过的方法，相当于欧式筛法的效果？）

    numbers = newNumbers

    echo &"numbers left: {numbers[0..min(10, high(numbers))]}... after sieved by {p}"

primes &= numbers # 把剩下的幸存者（一定是质数）捞上

echo "---Result---"

echo primes