#include<bits/stdc++.h>
using namespace std;

vector<int> primes;

void shieve(long long max)//线性筛，时间复杂度On 比埃氏筛Onloglogn还要快
{
    vector<bool> isPrime(max+1,true);
    for(int i = 2;i<=max;i++)
    {
        if(isPrime[i]) 
            primes.push_back(i);
        for(int p:primes){
            if(i*p>=max) break;
            isPrime[i*p] = false;
            if(i%p == 0) break;         //达到On的关键，只让最小的因子把数筛掉，例如筛掉12，只让2*6把他筛掉，不让4*3把他筛掉
        }

    }
}

int main() {
    int n;
    shieve(50000);
    while(cin>>n)
    {
   ...