1126.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1126 on 2005-10-27 at 20:47:04 */ 
#include <cstdio>
#include <cstring>

const int MAX = 10240;
const int LIMIT = 200000000;

bool prime[MAX] = {false};
int p[1280], pn = 0, psum[MAX];

int getSum(int);
int smith(int);

int main()
{
	int i, j;
	int n, m;
	
	prime[0] = prime[1] = true;
	for(i = 2; i < MAX; i++) {
		if(!prime[i]) {
			p[pn] = i;
			psum[pn++] = getSum(i);
			for(j = 2; i * j < MAX; j++) {
				prime[i*j] = true;
			}
		}
	}
	while(scanf("%d", &n) == 1) {
		if(n == 0) {
			return 0;
		} else {
			for(i = n+1; i < LIMIT; i++) {
				m = smith(i);
				if(m != -1 && m == getSum(i)) {
					printf("%d\n", i);
					break;
				}
			}
		}
	}
	
	return 0;
}

int getSum(int n)
{
	int sum = 0;
	while(n != 0) {
		sum += n % 10;
		n /= 10;
	}
	return sum;
}
int smith(int n)
{
	int l = 0, i;
	bool pr = true;
	if(n > MAX || prime[n]) {
		for(i = 0; i < pn && n != 1; i++) {
			while(n % p[i] == 0 && n != 1) {
				l += psum[i];
				n /= p[i];
				pr = false;
			}
		}
		if(n != 1) {
			l += getSum(n);
		}
	}
	if(pr) {
		return -1;
	} else {
		return l;
	}
}