#include #include using namespace std; #define MAX 10000000 bool zaru[MAX+1]; vector pr; int main(){ long long N; long long c=0; cin>>N; for(int i=2;i*i<=N;i++) zaru[i]=true; for(int i=2;i*i<=N;i++){ if(zaru[i]){ pr.push_back(i); for(int j=i*2;j*j<=N;j+=i) zaru[i]=false; } } for(int i=0;i