#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin>>n;
    if(n== 1){
        cout<<0<<endl;
        return 0;
    }
    
    // 用欧拉筛模板，线性时间复杂度生成n以内素数表，相当于完全背包问题的物品表，区别是01背包物品只能拿一次，完全背包无限次
    vector<bool> is_prime(n+1,true);
    vector<int> prime;
    for (int i=2;i<=n;i++) {
        if(is_prime[i]) 
            prime.push_back(i);
        for(auto &p:prime) {
            if (i * p > n) break;
            is_prime[i * p] = false;
            if (i % p == 0) break;
        }
    }
    
    int m=prime.size();
  &...