#include #include #include #include #include #include #include #include #include #include #include #include typedef long long ll; using namespace std; #define mod 1000003 #define INF 10000000 #define LLINF 2000000000000000000LL #define SIZE 100000 const int MAX_P = 10000000; bool prime[MAX_P+1]; void primen(void){ for(int i=2;i<=MAX_P;i++) prime[i]=true; for(int i=2;i*i<=MAX_P;i++) if(prime[i]) for(int j=i;i*j<=MAX_P;j++) prime[i*j]=false; } vector factor(ll n){ vector ret,ret2; for(ll i=1;i*i<=n;i++){ if(n%i==0){ ret.push_back(i); if(i*i fac; primen(); cin >> n; fac = factor(n); for(int i=1;i