# c++ – Algorithm error

## Question:

Coded an algorithm to check whether a number is exponential, it works well, but the check does not count 1 test. The first line contains the number of numbers to be checked, from 1 to 10 inclusive, then the numbers themselves from 1 to 10 to the 9th degree inclusive. The basic principle of the check is to decompose a number into prime factors, and if there is not a single prime factor that repeats, then the number is not a power.

``````#include <iostream>
#include <cmath>

using namespace std;
bool f(int b);

int main() {
int n, b;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> b;
if (step(b)) cout << "YES" << endl;
else cout << "NO" << endl;
}
}

bool f(int b)
{
long double T=2;
for (double i = 2; T>1.9; i++)
{
T = floor((pow(b, 1.0 / i)*1000000))/1000000;
if ((double)T == (int)T) return true;
}
return false;
}
``````

If the power numbers are those that can be obtained from a certain number by multiplying by itself at least once.

Here's a fairly fast algorithm based on the properties of the logarithm:

``````double log2Values(int x, int y) {
return log(x) / log(y);
}

bool f(int n)
{
for (int i = 2; i * i <= n; ++i) {
if (fabs(log2Values(n, i) - round(log2Values(n, i))) < 1e-7)
return true;
}
return false;
}
``````

And so if you enter the number `72` , then `"YES"` will be displayed, which is not correct.

The code above, although simple, is very long and not accurate. On numbers already more than 1 million, it may give incorrect values.

Fast and efficient code example provided by @StanislavVolodarskiy.

Scroll to Top