判断一个数是否是Smith数：是否是素数、分解因式、求个位数和。
输出10000以内的Smith数，发现Smith数的密度还是很高的，说明直接模拟应该不会超时。
以下是我的代码：
#include<iostream>
#include<math.h>
using namespace std;
bool isprime(long x)
{
if(x<=1) return false;
if(x==2) return true;
for(long i=2;i<=(long)sqrt(x)+1;i++)
if(x%i==0)
return false;
return true;
}
long digitsum(long x)
{
long re=0;
while(x>0)
{
re+=x%10;
x/=10;
}
return re;
}
bool Smith(long x)
{
long t=x,m=0,i;
if(isprime(x)) return false;
while(t%2==0)
{
m+=2;
t/=2;
}
i=3;
while(i<=(long)sqrt(t)+1)
{
if(t%i==0)
{
m+=digitsum(i);
t/=i;
}
else i+=2;
}
if(t>1)
{
m+=digitsum(t);
}
if(m==digitsum(x))
return true;
return false;
}
int main()
{
long T,n;
cin>>T;
while(T--)
{
cin>>n;
for(long i=n+1; ;i++)
if(Smith(i))
{
cout<<i<<endl;
break;
}
}
return 0;
}
posted on 2010-11-16 22:14
lee1r 阅读(509)
评论(1) 编辑 收藏 引用 所属分类:
题目分类：数学/数论