题目：http://poj.org/problem?id=1142
简单题，之前在joj上做过，而且直接枚举就过了，只是不明白的是为什么joj上那个代码交上去16ms，而现在这个交上去154ms，能优化的尽量优化也只是110ms
代码：
#include<cstdio> #include<cstring> #include<cmath> #define MAXN 32000 int is_prime[MAXN]; bool number[MAXN]; void find_prime() { memset(number, false, sizeof(number)); int cnt = 0; for(int i = 2; i < MAXN; ++ i) { if(!number[i]) { is_prime[cnt ++] = i; for(int j = i * i; j < MAXN; j += i) { number[j] = true;//写文章时发现这里写错了，居然还A了，改过来后果然是16ms } } } } int num_of_digit(int n) { int sum_digit = 0; while(n != 0) { sum_digit += n % 10; n /= 10; } return sum_digit; } bool is_smith_num(int n) { int s = num_of_digit(n); int sum_prime = 0; int m = sqrt(n); for(int i = 0; is_prime[i] <= m && n != 1; ++ i) { while(n % is_prime[i] == 0) { sum_prime += num_of_digit(is_prime[i]); n /= is_prime[i]; } } if(sum_prime == 0) { return false; } if(n > 1) { sum_prime += num_of_digit(n); } if(s == sum_prime) { return true; } return false; } int main() { freopen("poj1142.txt", "r", stdin); int N; find_prime(); while(scanf("%d", &N), N) { for(int n = N + 1; ; ++ n) { if(is_smith_num(n)) { printf("%d\n", n); break; } } } return 0; } |