code a jour

#include <QCoreApplication>
#include <QDebug>
#include <QList>
#include <QVector>
#include <QtMath>
#include <QElapsedTimer>

QList<quint64> primeList = {2,3,5,7,11};
const quint64 maxLevel = 1;
const quint64 update = 1000000;

quint64 nextPrime() {
    const quint64 lastPrime = primeList.last();
    quint64 testNumber = lastPrime + 2;
    quint64 limit = qCeil(qSqrt(testNumber));
    int index = 0;
    while(true) {
        if (testNumber % primeList.at(index) == 0) {
            testNumber += 2;
            limit = qCeil(qSqrt(testNumber));
            index = 0;
        } else if (index < primeList.count() && primeList.at(index) <= limit) {
            index++;
        } else {
            primeList.append(testNumber);
            return testNumber;
        }
    }
}

bool primeListContains(const quint64 number) {
    if (number > primeList.last()) {
        return false;
    }
    static quint64 min = 0;
    static quint64 max = primeList.count();
    static quint64 mid;
    static quint64 avg;
    while(max - min > 1) {
        avg = qFloor((min + max) / 2);
        mid = primeList.at(avg);
        if (number == mid) {
            return true;
        } else if (number > mid) {
            min = avg;
        } else if (number < mid) {
            max = avg;
        }
    }
    return number == primeList.at(min) || number == primeList.at(max);
}

QVector<quint64> getDecomposition(quint64 number) {
    QVector<quint64> decomp;
    decomp.reserve(32);
    int index = 0;
    quint64 limit = qCeil(qSqrt(number));
    quint64 prime;
    const int count = primeList.count();
    while(number > 1) {
        if (index >= count) {
            prime = nextPrime();
        } else {
            prime = primeList[index];
        }
        if (primeListContains(number) || prime > limit) {
            decomp.append(number);
            number = 1;
        } else if (number % prime == 0) {
            decomp.append(prime);
            number /= prime;
            limit = qCeil(qSqrt(number));
        } else {
            index++;
        }
    }
    return decomp;
}

QString recompose(const QVector<quint64>& decomp, const quint64 base = 10) {
    QString result = "";
    quint64 countRepeat = 1;
    quint64 previous = -1;
    const int count = decomp.count();
    for (int i = 0; i < count; i++) {
        quint64 prime = decomp[i];
        if (previous != prime) {
            if (countRepeat > 1) {
                result += QString::number(countRepeat, base);
            }
            countRepeat = 1;
            result += QString::number(prime, base);
            previous = prime;
        } else {
            countRepeat++;
        }
    }
    if (countRepeat > 1) {
        result += QString::number(countRepeat, base);
    }
    return result;
}

QString niceDecomp(const QVector<quint64>& decomp, const quint64 base) {
    QString result = "";
    int countRepeat = 1;
    quint64 previous = -1;
    const int count = decomp.count();
    for (int i = 0; i < count; i++) {
        quint64 prime = decomp[i];
        if (previous != prime) {
            if (countRepeat > 1) {
                result += "^" + QString::number(countRepeat, base);
            }
            countRepeat = 1;
            if (!result.isEmpty()) {
                result += " x ";
            }
            result += QString::number(prime, base);
            previous = prime;
        } else {
            countRepeat++;
        }
    }
    if (countRepeat > 1) {
        result += "^" + QString::number(countRepeat, base);
    }
    return result;
}

bool check(quint64 i, const QVector<quint64>& decomp, quint64 b, quint64 objective, quint64 level) {
    quint64  parsed = recompose(decomp, b).toInt(Q_NULLPTR, b);
    bool subresult = false;
    if (i > parsed && level < maxLevel) {
        QVector<quint64> nextdecomp = getDecomposition(parsed);
        subresult = check(parsed, nextdecomp, b, i, level + 1);
    }
    if (subresult || (decomp.count() > 1 && objective == parsed)) {
        qDebug() << "* BASE:" << b << ":  \t"
                 << qPrintable(QString::number(i, b)) << qPrintable("(" + QString::number(i) + ")") << qPrintable("=")
                 << qPrintable(niceDecomp(decomp, b)) << qPrintable("(" + niceDecomp(decomp, 10) + ")");
        return true;
    }
    return false;
}

void find(quint64 start, quint64 max, quint64 minbase, quint64 maxBase) {
    QElapsedTimer timer;
    timer.start();
    int previousElapsed;
    for (quint64 i = start; i < max; i++) {
        QVector<quint64> decomp = getDecomposition(i);
        if (i % update == 0) {
            qDebug() << i << "took" << timer.elapsed() - previousElapsed << "\tprime count"
                     << primeList.count() << "\tbiggest prime" << primeList.last() << "\telapsed" << timer.elapsed();
            previousElapsed = timer.elapsed();
        }
        for (quint64 b = minbase; b <= maxBase; b++) {
            check(i, decomp, b, i, 0);
        }
    }
    qDebug() << "FINISH: from" << start << "to" << max << "in base" << minbase << "to" << maxBase << "took" << timer.elapsed() / 1000 << "seconds";
}

int main(int argc, char *argv[])
{
    Q_UNUSED(argc)
    Q_UNUSED(argv)
    find(1, UINT64_MAX, 2, 36);
    return 0;
}