This problem is difficult. By using the sieve method and strengthening it, after multiplying the prime factors of each number and sorting them, we can determine what the next sequence will be.
2 4 8 16 32 ........3 6 9
So if the product of the prime factors of the next number is not the same as the previous one, it means it has exceeded the MAX range.
//============================================================================
// Name : Next Same-Factored.cpp
// Date : 2013/3/30 12:42:53 AM
// Author : GCA
//============================================================================
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <climits>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cctype>
#include <utility>
using namespace std;
#ifdef ONLINE_JUDGE
#define ll "%lld"
#else
#define ll "%I64d"
#endif
typedef unsigned int uint;
typedef long long int Int;
#define Set(a,s) memset(a,s,sizeof(a))
#define Write(w) freopen(w,"w",stdout)
#define Read(r) freopen(r,"r",stdin)
#define Pln() printf("\\n")
#define I_de(x,n)for(int i=0;i<n;i++)printf("%d ",x[i]);Pln()
#define De(x)printf(#x"%d\\n",x)
#define For(i,x)for(int i=0;i<x;i++)
#define CON(x,y) x##y
#define Pmz(dp,nx,ny)for(int hty=0;hty<ny;hty++){for(int htx=0;htx<nx;htx++){\\
printf("%d ",dp[htx][hty]);}Pln();}
#define M 2000001
#define PII pair<int,int>
#define PB push_back
#define oo INT_MAX
#define Set_oo 0x3f
#define Is_debug true
#define debug(...) if(Is_debug)printf("DEBUG: "),printf(__VA_ARGS__)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define eps 1e-6
bool xdy(double x,double y){return x>y+eps;}
bool xddy(double x,double y){return x>y-eps;}
bool xcy(double x,double y){return x<y-eps;}
bool xcdy(double x,double y){return x<y+eps;}
int min3(int x,int y,int z){
int tmp=min(x,y);
return min(tmp,z);
}
int max3(int x,int y,int z){
int tmp=max(x,y);
return max(tmp,z);
}
struct nums{
int primesum;
int all;
int tmp;
}num[M];
int sid[M];
bool cmp(nums a,nums b){
if(a.primesum<b.primesum){
return true;
}else if(a.primesum>b.primesum){
return false;
}else{
return a.all<b.all;
}
}
int main() {
ios_base::sync_with_stdio(0);
for(int i=0;i<M;i++){
num[i].tmp=num[i].all=i;
num[i].primesum=1;
}
for(int i=2;i<M;i++){
if(num[i].all==num[i].tmp){
num[i].primesum=i;
for(int prime=(i<<1);prime<M;prime+=i){
num[prime].primesum*=i;
num[prime].tmp/=i;
}
}
}
sort(num,num+M,cmp);
for(int i=0;i<M;i++){
sid[num[i].all]=i;
// debug("%d",num[i].all);
}
int n;
while(~scanf("%d",&n)){
if(n==0||n==1){
puts("Not Exist!");
continue;
}
n=sid[n];
// debug("%d",num[n+1].all);
if(num[n].primesum==num[n+1].primesum){
if(num[n+1].all<=2000000)
printf("%d\\n",num[n+1].all);
else puts("Not Exist!");
}else puts("Not Exist!");
}
}