import strutils, strformat

 

    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] = @[]

 

    if p * p > n:

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

        #自己是上一轮的幸存者，这一轮没有改变numbers，所以不需要加入素数

 

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

 

    for i, v in numbers:

        if v mod p != 0: # 不能被用来筛的质数整除，所以不知道是不是质数

            newNumbers.add(v) # 接着筛

        # 否则就淘汰，下一次不用筛了（这好像是一种优化过的方法，相当于欧式筛法的效果？）

 

    numbers = newNumbers

 

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

 

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

 

echo "---Result---"

 

echo primes