A - Smith Numbers POJ
2024-10-09 01:01:43
While skimming his phone directory in 1982, Albert Wilansky, a mathematician of Lehigh University,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:
4937775= 3*5*5*65837
The sum of all digits of the telephone number is 4+9+3+7+7+7+5= 42,and the sum of the digits of its prime factors is equally 3+5+5+6+5+8+3+7=42. Wilansky was so amazed by his discovery that he named this kind of numbers after his brother-in-law: Smith numbers.
As this observation is also true for every prime number, Wilansky decided later that a (simple and unsophisticated) prime number is not worth being a Smith number, so he excluded them from the definition.
Wilansky published an article about Smith numbers in the Two Year College Mathematics Journal and was able to present a whole collection of different Smith numbers: For example, 9985 is a Smith number and so is 6036. However,Wilansky was not able to find a Smith number that was larger than the telephone number of his brother-in-law. It is your task to find Smith numbers that are larger than 4937775!
4937775= 3*5*5*65837
The sum of all digits of the telephone number is 4+9+3+7+7+7+5= 42,and the sum of the digits of its prime factors is equally 3+5+5+6+5+8+3+7=42. Wilansky was so amazed by his discovery that he named this kind of numbers after his brother-in-law: Smith numbers.
As this observation is also true for every prime number, Wilansky decided later that a (simple and unsophisticated) prime number is not worth being a Smith number, so he excluded them from the definition.
Wilansky published an article about Smith numbers in the Two Year College Mathematics Journal and was able to present a whole collection of different Smith numbers: For example, 9985 is a Smith number and so is 6036. However,Wilansky was not able to find a Smith number that was larger than the telephone number of his brother-in-law. It is your task to find Smith numbers that are larger than 4937775!
Input
The input file consists of a sequence of positive integers, one integer per line. Each integer will have at most 8 digits. The input is terminated by a line containing the number 0.
Output
For every number n > 0 in the input, you are to compute the smallest Smith number which is larger than n,and print it on a line by itself. You can assume that such a number exists.
Sample Input
4937774
0
题目大意:
给你一个数,求大于这个数字并满足以下条件的最小值:
条件:数字的各个位置加起来与用质数拆分该数字后得到的数字的各个位置之和相等 4937775= 3*5*5*65837
暴力模拟就可以啦 首先要知道质数拆分,然后将得到的每个数字的各个位置相加相等。如果与原数字相等的话说明找到啦!
#include<iostream>
#include<cstdio>
using namespace std; int check(int x){//由于数字范围太大,不能打表,只能这样一步一步来
for(int i=;i*i<=x;i++){
if(x%i==) return ;
}
return ;
} int f2(int x){
int sum=;
while(x){
sum+=x%;
x=x/;
}
return sum;
}
int f(int x){
int sum=;
for(int i=;i*i<=x;i++){//拆分
if(x%i==){
int ans=;
if(i<)
{
while(x%i==){
ans++;
x=x/i;
}
sum+=i*ans;
}
else {
int s=f2(i);
while(x%i==){
ans++;
x=x/i;
}
sum+=s*ans;
}
}
}
if(x>) sum+=f2(x);
return sum;
}
int main(){
int n;
while(scanf("%d",&n)!=EOF&&n){
for(int i=n+;;i++){
if(check(i)==){
if(f2(i)==f(i)){
printf("%d\n",i);
break;
} }
}
}
return ;
}
最新文章
- 文件服务器:FTP服务器详解
- Java数组与vector互转
- Python札记 -- 文件压缩
- 2016 年 Python 开发者调查结果
- Hadoop学习总结之五:Hadoop的运行痕迹
- js学习笔记之:数组(一)
- Spring Boot + Elasticsearch
- MySQL中的concat函数
- JavaWeb---javabean
- iOS手势冲突问题
- 对于bootstrap可视化布局设计可以参考2017.6.2
- Exp4 恶意代码分析 20164314
- jquery判断点击事件是否指定区域
- javaWeb-Servlet工作原理
- python安装与pip操作
- tvs二极管应用电路
- Oracle 命令
- Window下JDK安装教程
- C++ 重载 重写 重定义
- P2916 [USACO08NOV]安慰奶牛Cheering up the Cow
热门文章
- tcp/ip面试题
- Python python 函数参数:必选参数,默认参数
- iOS pch
- Vue 里面对树状数组进行增删改查 的方法
- Javascript-什么是递归?
- VirtualBox 安装 Arch Linux 并配置桌面环境
- sql.Rows 转换为 []map[string]interface{} 类型
- ajax2.0之文件上传加跨域
- 浅谈动态规划(Dynamic Programming)
- SSM 三大框架系列:Spring 5 + Spring MVC 5 + MyBatis 3.5 整合(附源码)