if we assume non trivial cases then the constraints would be something like this:
This can be solved by sieves that mark all powers bigger then 1 up to N of the result. Now the question is do you need to optimize single query or many of them ? If you need just single query then you do not need the sieve table in memory, you just iterate until hit the N and then stop (so in worst case when N is not in form P^Q this would compute the whole sieve). Otherwise init such table once and then just use it. As N is small I go for the full table.
const int n=100000;
int sieve[n]={255}; // for simplicity 1 int/number but it is waste of space can use 1 bit per number instead
int powers(int x)
{
// init sieve table if not already inited
if (sieve[0]==255)
{
int i,p;
for (i=0;i<n;i++) sieve[i]=0; // clear sieve
for (p=sqrt(n);p>1;p--) // process all non trivial P
for (i=p*p;i<n;i*=p) // go through whole table
sieve[i]=p; // store P so it can be easily found later (if use 1bit/number then just set the bit instead)
}
return sieve[x];
}
- first call took
0.548 ms on mine setup the others are non measurable small times
- it returns the
P so if P!=0 the number is in form P^Q so you can use it as bool directly, and also you can easily get Q by dividing or you can create another sieve with Q to be even more fast if you need also the P,Q
Here all found non trivial powers N<100000
4 = 2^q
8 = 2^q
9 = 3^q
16 = 2^q
25 = 5^q
27 = 3^q
32 = 2^q
36 = 6^q
49 = 7^q
64 = 2^q
81 = 3^q
100 = 10^q
121 = 11^q
125 = 5^q
128 = 2^q
144 = 12^q
169 = 13^q
196 = 14^q
216 = 6^q
225 = 15^q
243 = 3^q
256 = 2^q
289 = 17^q
324 = 18^q
343 = 7^q
361 = 19^q
400 = 20^q
441 = 21^q
484 = 22^q
512 = 2^q
529 = 23^q
576 = 24^q
625 = 5^q
676 = 26^q
729 = 3^q
784 = 28^q
841 = 29^q
900 = 30^q
961 = 31^q
1000 = 10^q
1024 = 2^q
1089 = 33^q
1156 = 34^q
1225 = 35^q
1296 = 6^q
1331 = 11^q
1369 = 37^q
1444 = 38^q
1521 = 39^q
1600 = 40^q
1681 = 41^q
1728 = 12^q
1764 = 42^q
1849 = 43^q
1936 = 44^q
2025 = 45^q
2048 = 2^q
2116 = 46^q
2187 = 3^q
2197 = 13^q
2209 = 47^q
2304 = 48^q
2401 = 7^q
2500 = 50^q
2601 = 51^q
2704 = 52^q
2744 = 14^q
2809 = 53^q
2916 = 54^q
3025 = 55^q
3125 = 5^q
3136 = 56^q
3249 = 57^q
3364 = 58^q
3375 = 15^q
3481 = 59^q
3600 = 60^q
3721 = 61^q
3844 = 62^q
3969 = 63^q
4096 = 2^q
4225 = 65^q
4356 = 66^q
4489 = 67^q
4624 = 68^q
4761 = 69^q
4900 = 70^q
4913 = 17^q
5041 = 71^q
5184 = 72^q
5329 = 73^q
5476 = 74^q
5625 = 75^q
5776 = 76^q
5832 = 18^q
5929 = 77^q
6084 = 78^q
6241 = 79^q
6400 = 80^q
6561 = 3^q
6724 = 82^q
6859 = 19^q
6889 = 83^q
7056 = 84^q
7225 = 85^q
7396 = 86^q
7569 = 87^q
7744 = 88^q
7776 = 6^q
7921 = 89^q
8000 = 20^q
8100 = 90^q
8192 = 2^q
8281 = 91^q
8464 = 92^q
8649 = 93^q
8836 = 94^q
9025 = 95^q
9216 = 96^q
9261 = 21^q
9409 = 97^q
9604 = 98^q
9801 = 99^q
10000 = 10^q
10201 = 101^q
10404 = 102^q
10609 = 103^q
10648 = 22^q
10816 = 104^q
11025 = 105^q
11236 = 106^q
11449 = 107^q
11664 = 108^q
11881 = 109^q
12100 = 110^q
12167 = 23^q
12321 = 111^q
12544 = 112^q
12769 = 113^q
12996 = 114^q
13225 = 115^q
13456 = 116^q
13689 = 117^q
13824 = 24^q
13924 = 118^q
14161 = 119^q
14400 = 120^q
14641 = 11^q
14884 = 122^q
15129 = 123^q
15376 = 124^q
15625 = 5^q
15876 = 126^q
16129 = 127^q
16384 = 2^q
16641 = 129^q
16807 = 7^q
16900 = 130^q
17161 = 131^q
17424 = 132^q
17576 = 26^q
17689 = 133^q
17956 = 134^q
18225 = 135^q
18496 = 136^q
18769 = 137^q
19044 = 138^q
19321 = 139^q
19600 = 140^q
19683 = 3^q
19881 = 141^q
20164 = 142^q
20449 = 143^q
20736 = 12^q
21025 = 145^q
21316 = 146^q
21609 = 147^q
21904 = 148^q
21952 = 28^q
22201 = 149^q
22500 = 150^q
22801 = 151^q
23104 = 152^q
23409 = 153^q
23716 = 154^q
24025 = 155^q
24336 = 156^q
24389 = 29^q
24649 = 157^q
24964 = 158^q
25281 = 159^q
25600 = 160^q
25921 = 161^q
26244 = 162^q
26569 = 163^q
26896 = 164^q
27000 = 30^q
27225 = 165^q
27556 = 166^q
27889 = 167^q
28224 = 168^q
28561 = 13^q
28900 = 170^q
29241 = 171^q
29584 = 172^q
29791 = 31^q
29929 = 173^q
30276 = 174^q
30625 = 175^q
30976 = 176^q
31329 = 177^q
31684 = 178^q
32041 = 179^q
32400 = 180^q
32761 = 181^q
32768 = 2^q
33124 = 182^q
33489 = 183^q
33856 = 184^q
34225 = 185^q
34596 = 186^q
34969 = 187^q
35344 = 188^q
35721 = 189^q
35937 = 33^q
36100 = 190^q
36481 = 191^q
36864 = 192^q
37249 = 193^q
37636 = 194^q
38025 = 195^q
38416 = 14^q
38809 = 197^q
39204 = 198^q
39304 = 34^q
39601 = 199^q
40000 = 200^q
40401 = 201^q
40804 = 202^q
41209 = 203^q
41616 = 204^q
42025 = 205^q
42436 = 206^q
42849 = 207^q
42875 = 35^q
43264 = 208^q
43681 = 209^q
44100 = 210^q
44521 = 211^q
44944 = 212^q
45369 = 213^q
45796 = 214^q
46225 = 215^q
46656 = 6^q
47089 = 217^q
47524 = 218^q
47961 = 219^q
48400 = 220^q
48841 = 221^q
49284 = 222^q
49729 = 223^q
50176 = 224^q
50625 = 15^q
50653 = 37^q
51076 = 226^q
51529 = 227^q
51984 = 228^q
52441 = 229^q
52900 = 230^q
53361 = 231^q
53824 = 232^q
54289 = 233^q
54756 = 234^q
54872 = 38^q
55225 = 235^q
55696 = 236^q
56169 = 237^q
56644 = 238^q
57121 = 239^q
57600 = 240^q
58081 = 241^q
58564 = 242^q
59049 = 3^q
59319 = 39^q
59536 = 244^q
60025 = 245^q
60516 = 246^q
61009 = 247^q
61504 = 248^q
62001 = 249^q
62500 = 250^q
63001 = 251^q
63504 = 252^q
64000 = 40^q
64009 = 253^q
64516 = 254^q
65025 = 255^q
65536 = 2^q
66049 = 257^q
66564 = 258^q
67081 = 259^q
67600 = 260^q
68121 = 261^q
68644 = 262^q
68921 = 41^q
69169 = 263^q
69696 = 264^q
70225 = 265^q
70756 = 266^q
71289 = 267^q
71824 = 268^q
72361 = 269^q
72900 = 270^q
73441 = 271^q
73984 = 272^q
74088 = 42^q
74529 = 273^q
75076 = 274^q
75625 = 275^q
76176 = 276^q
76729 = 277^q
77284 = 278^q
77841 = 279^q
78125 = 5^q
78400 = 280^q
78961 = 281^q
79507 = 43^q
79524 = 282^q
80089 = 283^q
80656 = 284^q
81225 = 285^q
81796 = 286^q
82369 = 287^q
82944 = 288^q
83521 = 17^q
84100 = 290^q
84681 = 291^q
85184 = 44^q
85264 = 292^q
85849 = 293^q
86436 = 294^q
87025 = 295^q
87616 = 296^q
88209 = 297^q
88804 = 298^q
89401 = 299^q
90000 = 300^q
90601 = 301^q
91125 = 45^q
91204 = 302^q
91809 = 303^q
92416 = 304^q
93025 = 305^q
93636 = 306^q
94249 = 307^q
94864 = 308^q
95481 = 309^q
96100 = 310^q
96721 = 311^q
97336 = 46^q
97344 = 312^q
97969 = 313^q
98596 = 314^q
99225 = 315^q
99856 = 316^q
- it took
62.6 ms including first init call (and string output to memo which is much slower then the computation itself) without the string it took just 1.25 ms
与恶龙缠斗过久,自身亦成为恶龙；凝视深渊过久,深渊将回以凝视…
