#include <algorithm> #include <bits/stdc++.h> #include <vector> using namespace std ; const int N=1e6+5; vector<int> prime(N); vector<bool> vis(N); int idx=0; void Euler(){ for(int i = 2; i <= N; i++) { if(!vis[i]) prime[++idx] = i; for(int j = 1; prime[j]*i <= N;...