範例程式碼 uva10042

//uva10042
#include <iostream>
#include <cstring>
#include <cstdio>

#define PRIME_MAX 40000

using namespace std;

void MakePrime(int Prime[], int &cnt) {
	int *table = new int [PRIME_MAX];
	int i, j, k;

	memset(table, 0, sizeof(table));

	for(i = 2; i < PRIME_MAX; ++i) {
		if(!table[i]) {
			Prime[cnt++] = i;
			for(j = 2; i * j < PRIME_MAX; ++j)
				table[i * j] = 1;
		}
	}
}

int SumDigit(int n) {
	int sum = 0;

	while(n > 0) {
		sum += (n % 10);
		n /= 10;
	}

	return sum;
}

int FactorSumDigit(int Prime[], int PrimeCnt, int n) {
	int i, k;
	int sum = 0;

	for(i = 0; i < PrimeCnt && Prime[i] < n; ++i) {
		if(!(n % Prime[i])) {
			// n = Prime[i]^k * n';
			for(k = 0; !(n % Prime[i]); ++k)
				n /= Prime[i];

			// so, SumDigit(Prime[i]) only need once.
			sum += (SumDigit(Prime[i]) * k);
		}
	}

	if(n != 1)	// n is prime now.
		sum += SumDigit(n);

	return sum;
}

int IsPrime(int Prime[], int PrimeCnt, int n) {
	int flag = 1, i;
	for(i = 0; i < PrimeCnt && Prime[i] * Prime[i] <= n; ++i) {
		if(!(n % Prime[i])) {
			flag = 0;
			break;
		}
	}

	// 1 -> IsPrime, 0 -> NotPrime.
	return flag;
}

int main() {
	int *Prime = new int [PRIME_MAX];
	int PrimeCnt = 0;

	MakePrime(Prime, PrimeCnt);

	int t;
	cin >> t;

	while(t--) {
		int n;
		cin >> n;

		// answer is > n (by definition from problem).
		++n;

		// n != prime && S(n) == FS(n) break!
		// linear search is enough.
		while(IsPrime(Prime, PrimeCnt, n) || SumDigit(n) != FactorSumDigit(Prime, PrimeCnt, n))
			++n;

		cout << n << endl;
	}

	return 0;
}