c++ – Algorithm error


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