原创：Smith Numbers - PC110706

作者：MilkCu

题目描述

Smith Numbers

While skimming his phone directory in 1982, mathematician Albert Wilansky noticed that the telephone number of his brother-in-law H. Smith had the following peculiar property: The sum of the digits of that number was equal to the sum of the digits of the prime factors of that number. Got it? Smith‘s telephone number was 493-7775. This number can be written as the product of its prime factors in the following way:

As this property is true for every prime number, Wilansky excluded them from the definition. Other Smith numbers include 6,036 and 9,985.

Wilansky was not able to find a Smith number which was larger than the telephone number of his brother-in-law. Can you help him out?

Input

Output

Sample Input

1
4937774

Sample Output

4937775

解题思路

如何找出素因子呢？枚举法。

那每个整数的素因子是否唯一呢？
由算术基本定理可得，每个整数表示成素数乘积的方式只有一种。

Smith数肯定是合数，且满足各个数字之和等于所有素因子的每个数字之和。
注意，素因子中可能出现两个相同的数字。

那样就可以按部就班的做，从给定的数开始遍历，找到满足的数就退出循环。

为什么会超时呢？构建一个装有素数的容器。

为什么答案错误呢？
注意：若临时变量tc不为1，则说明它超出了sqrt(1e9)的范围，但它是质数，仍是该整数的质因子。

代码实现

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> v;
int isPrime(int x) {
	if(x == 2) {
		return 1;
	}
	int s = ceil(sqrt(x));
	for(int i = 2; i <= s; i++) {
		if(x % i == 0) {
			return 0;
		}
	}
	return 1;
}
void getPrime(void) {
	int s = ceil(sqrt(1e9));
	for(int i = 2; i <= s; i++) {
		if(isPrime(i)) {
			v.push_back(i);
		}
	}
}
int calc(int x) {
	int sum = 0;
	while(x) {
		sum += x % 10;
		x /= 10;
	}
	return sum;
}
int smith(int n) {
	int current = n + 1;
	while(1) {
		//if(find(v.begin(), v.end(), current) != v.end()) {
		if(isPrime(current)) {
			//zhishu
			current++;
			continue;
		}
		int csum = calc(current);
		int tc = current;
		int tsum = 0;
		for(int i = 0; i < v.size(); i++) {
			while(tc % v[i] == 0) {
				//cout << tc << " " << v[i] << endl;
				tc /= v[i];
				tsum += calc(v[i]);
			}
		}
		if(tc != 1) {
			tsum += calc(tc);  //注意！！ 
		}
		//cout << current << " " << csum << " " << tsum << endl;
		if(tsum == csum) {
			return current;
		}
		//break;
		current++;
	}
}
void print(int x) {
	cout << x << " ";
}
int main(void) {
	//cout << isPrime(4937775) << endl;
	//cout << calc(4937775) << endl;
	int m;
	getPrime();
	//for_each(v.begin(), v.end(), print);
	//cout << endl;
	cin >> m;
	while(m--) {
		int n;
		cin >> n;
		cout << smith(n) << endl;
	}
	return 0;
}

（全文完）

本文地址：http://blog.csdn.net/milkcu/article/details/23607205

Smith Numbers - PC110706,布布扣,bubuko.com

Smith Numbers - PC110706

原文：http://blog.csdn.net/milkcu/article/details/23607205