# 先前那个错了啦，我是傻逼
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
