UVa 10042 - Smith Numbers

#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS 1
#endif

#include <iostream>
#include <sstream>
#include <cmath>
#include <vector>

using namespace std;

const int maxVal = 10e6;
bool sieve[maxVal];

int nextInt()
{
    int next;
    scanf("%d", &next);
    return next;
}

int sumDigits(int num)
{
    string sNum = to_string(num);
    int sum = 0;
    for (int i = 0; i < sNum.length(); i++)
    {
        string val = sNum.substr(i, 1);
        sum += stoi(val);
    }
    return sum;
}

bool isPrime(int n)
{
    return (n < maxVal && !sieve[n]);
}

int main()
{
    // Load sieve array.
    sieve[0] = true;
    sieve[1] = true;

    for (int i = 2; i*i <= maxVal; i++)
        if (!sieve[i])
            for (int j = i * 2; j < maxVal; j += i)
                sieve[j] = true;

    // Load prime array.
    vector<int> primes;
    primes.reserve(10000);

    for (int i = 0; i < maxVal; i++)
    {
        if (!sieve[i])
            primes.push_back(i);
    }

    int numCases = nextInt();

    for (int t = 0; t < numCases; t++)
    {
        int num = nextInt();
        int nDigitSum = 0;
        int primeSum = -1;

        while (nDigitSum != primeSum)
        {
            int nextNum = ++num;
            nDigitSum = sumDigits(num);
            primeSum = 0;

            if (!isPrime(nextNum))
            {
                int i = 0;

                while (i < maxVal && pow(primes[i], 2) <= nextNum)
                {
                    if (nextNum % primes[i] == 0)
                    {
                        int factorSum = sumDigits(primes[i]);
                        while (nextNum % primes[i] == 0)
                        {
                            nextNum /= primes[i];
                            primeSum += factorSum;
                        }
                    }

                    i++;
                }

                if (num != nextNum && nextNum != 1)
                    primeSum += sumDigits(nextNum);
            }
        }

        printf("%d\n", num);
    }

    return 0;
}