/**
题目：The Super Powers UVA 11752
链接：https://vjudge.net/contest/154246#problem/Y
题意：求无符号长整形以内的数满足至少可以用两种不同的次方来表示。比如64 = 2^6 = 8^2； 一个数的1次方不算数。
思路：
分析过程如下：
1 = 1^1 1^2 1^3
16 = 2^4 4^2
64 = 2^6 8^2
81 = 3^4 9^2
256 = 2^8 16^2
512 = 2^9 8^3 设Max为最大的可能获得的值。
Max = a^e1 or a^e2 or ... (2<=e1<e2) a <= Max开三次方根=[1,1e7] 前面我猜想一个满足条件的数是某一个素因子的合数次方。 (2*3)^4 = (4*9)^2 含有多个素数。实际上不止一个素因子。 那么底数在（Max开三次方根）内是任意可能的。 有一点可以肯定：一个数的合数次方一定是满足条件的数。 底数在[1,1e7]以内。然后合数范围在64以内。然后set存数并去重；时间复杂度过大。 避免使用set？尝试提前去重。 2^4, 2^6, 2^8, 2^9, 2^10, 2^12, 2^14, 2^15. 取2^8 = 4^4 重复了。 2^12 = 4^6 = 8^4 （保证幂是合数） 重复了。 而：2^4, 2^6, 2^9, 2^10, 2^14, 2^15不会再重复。因为幂都是两个素数相乘的结果。 如何通过现在的某些计算来预测将来的某些数不用再重复计算？
或者通过一些计算来判定当前的数已经算过了。 4^4， 4^6， 4^8， 4^9， 4^10， 4^12. 好像这些都是重复了的。那么。。。所有的底数为合数都会被重复。 只要计算底数为素数的就行了？ (2*3)^4 = (4*9)^2 含有多个素数。从哪里得来？ 再试试其他合数为底数的情况。 6^4, 6^6, 6^5, 6^8, 6^9, 6^10. 6^4没有重复过。并不是所有的底数为合数都会被重复。 2^12 = 8^4 可以得知如果以前出现过。那么底数应该可以开根号才行，即底数可以表示成一个数的次方，次方>1。 新结论：底数如果是某个数的次方，那么它的所有合数幂都重复过。其他情况均没有重复过。 问题好像重复了。都是某个数的次方。只不过题目为至少两个。 那么对每一个非次方数的底数a。它的贡献为a^e. (e为合数，且a^e<=2^64 - 1) 还是往这方面处理：如何通过现在的某些计算来预测将来的某些数不用再重复计算？ 预处理64以内的合数的约数对，即：两个约数相乘等于本身为一对。这样通过约束对来判断是否那些底数会重复。 当两个约数至少一个>=4的合数时候，比如d1,d2；那么(x^d1)^d2 or (x^d2)^d1 都要去重。 解题方法：
预处理64以内的约数。以及每一个约数的约数对。
枚举底数a在[1,1e7]内。
对每一个底数a枚举它约数次方。并如果次方可以分解成两个约数，其中一个是>=4的约数。那么底数^另一个约数形成的数不能再作为计算的底数。 猜想：如果时间超限，适当降低[1,1e7]右边界的范围。 为了避免底数的合数次方超出unsigned long long 范围，所以用log对数来处理。 其实应该可以很快想到的，但是走了很多弯路。积累经验。多思考。
*/ #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include<vector>
#include <cmath>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e5+;
const double eps = 1e-;
vector<int> v[];//存储约数对。
int isHe[];//isHe[i] == 1表示这是一个合数。
int he[], z;//存储合数。
ull ans[], cnt;//注意这里不能和maxn一直相同。因为ans数量可能更多。
//经测试最多67385个；
int flag[maxn];
ll f(ll a,ll b)
{
ll p = ;
while(b){
if(b&) p*=a;
a = a*a;
b >>= ;
}
return p;
}
void init()
{
memset(isHe, , sizeof isHe);
for(int i = ; i < ; i++){
if(isHe[i]==){
for(int j = i*i; j < ; j+=i){
isHe[j] = ;
}
}
}
z = ;
for(int i = ; i < ; i++){
if(isHe[i]){
he[z++] = i;
for(int j = ; j*j < ; j++){
if(i%j==){
if(he[j]||he[i/j]){
v[i].push_back(j);
v[i].push_back(i/j);
}
}
}
}
}
ull mas = (<<)-;
//cout<<"mas = "<<mas<<endl;
cnt = ;
for(int i = ; i < maxn; i++){
if(flag[i]) continue;
ull p = i, num = ;
for(int j = ; j < z; j++){
if(he[j]>log(mas)/log(i)-eps) break;///不加eps，会存在误差，比如2^64次方可能会算进去。然后p = 0;
while(num<he[j]){
num++;
p *= i;
}
if(num<he[j]) break;
ans[cnt++] = p;
int len = v[he[j]].size();
for(int k = ; k < len; k+=){
if(isHe[v[he[j]][k]]){
ull temp = f(i,v[he[j]][k+]);
if(temp>=maxn) continue;
flag[temp] = ;
}
if(isHe[v[he[j]][k+]]){
ull temp = f(i,v[he[j]][k]);
if(temp>=maxn) continue;
flag[temp] = ;
}
}
}
}
sort(ans,ans+cnt);
printf("1\n");
for(int i = ; i < cnt; i++){
printf("%llu\n",ans[i]);
}
}
int main()
{
init(); return ;
}