Form Of Number

general
, ,
1

How can we check whether a number(n) is in the form a power b (a^b, b>=2)?

2

There are about [log(n,a)] possible values of b. Now if a=2 then bmax=[log(n,2)] which is very small. So you can simply use brute force through the values of b from 2 to bmax to check if there exists a such that a^b=n.

Here’s my solution - ideone

3

good query…i have been looking for this answer since long time :smiley:

4 Likes
4

This may help:
http://cr.yp.to/papers/powers.pdf,
http://cr.yp.to/lineartime/powers2-20050509.pdf

5

Check if ( log(b) / log(a) ) = (int) ( log(b) / log(a) )

If yes then it is of from a^b.

Code

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
    if( ( log(a) / log(b) ) == (int) ( log(a)/log(b) ) ) printf("yes");
    else printf("no");
    return 0;
}