判斷一個數是否是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 閱讀(521)
評論(1) 編輯 收藏 引用 所屬分類:
題目分類：數學/數論