c++ - Finding whether a number has P^Q form or not?

Question

I have recently appeared online coding Test. I was struck one question i.e

A number N is given finding the above number is P^Q(P power Q) form or not. I did the question using Brute force method (satisfying for individual number) but that result in time out. SO I need Efficient algorithm.

Input: 9

out put : yes

Input: 125

out put : yes

Input: 27

out put : yes

Constraints: 2<N<100000

Answer 1

if we assume non trivial cases then the constraints would be something like this:

• N = <2,100000)
• P>1
• Q>1

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