题解 | 筛选法求素数

n=int(input())
flag=[1]*(n+1)
flag[0]=flag[1]=0
primes=[]*n
for i in range(2,n+1):    
    if flag[i]==1:
        primes.append(i)
    for p in primes:
        if p*i>n:
            break
        flag[p*i]=0
        if i%p==0:
            break
            
print(*primes)            
print(n-len(primes)-1)