Smith Numbers

逃离我推掉我的手 2022-05-18 00:10 122阅读 0赞

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!  
**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  
**Sample Output**  
4937775

--------------------

给一个数，找到比这个数大的数x，x需要满足各位数和与其分解质因子之后的位数和相同  
设f(x)为x的位数和

则f(x)=f(x的因子)  f ( x ) = f ( x 的 因 子 )

eg:

4937775=3∗5∗5∗65837  4937775 = 3 ∗ 5 ∗ 5 ∗ 65837

4\+9\+3\+7\+7\+7\+5=42  4 + 9 + 3 + 7 + 7 + 7 + 5 = 42

3\+5\+5\+6\+5\+8\+3\+7=42  3 + 5 + 5 + 6 + 5 + 8 + 3 + 7 = 42

--------------------

code

//#include<bits/stdc++.h>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    using  namespace std;
    typedef long long ll;
    const int MAXN=1e5+5;
    int prime[MAXN+1];
    int factor[1000][2];
    int isprime(int n)
    {
        for(int i=2;i*i<=n;i++)
            if(n%i==0)  return 0;
        return n>1;
    }
    void getprime()
    {
        memset(prime,0,sizeof(prime));
        for(int i=2;i<=MAXN;i++)
        {
            if(!prime[i])   prime[++prime[0]]=i;
            for(int j=2;j*i<=MAXN;j++)
                prime[i*j]=1;
        }
    }
    int getfactor(int n)
    {
        int cnt=0;
        memset(factor,0,sizeof(factor));
        for(int i=1;prime[i]*prime[i]<=n;i++)
        {
            factor[cnt][1]=0;//第二个元素记录幂 
            if(n%prime[i]==0)
            {
                factor[cnt][0]=prime[i];
                while(n%prime[i]==0)
                {
                    n/=prime[i];
                    factor[cnt][1]++;
                }
                cnt++;
            }
        }
        if(n!=1)
        {
            factor[cnt][0]=n;
            factor[cnt++][1]=1;
        }
        return cnt;
    }
    int f(int n)
    {
        int ans=0;
        while(n)
        {
            ans+=n%10;
            n/=10;
        }
        return ans;
    }
    int cnt(int n)
    {
        if(isprime(n))
            return f(n);
        for(int i=(int)sqrt(n+0.5);i>1;i--)
            if(n%i==0)  return cnt(i)+cnt(n/i);
     } 
    int main()
    {
        int n;
        getprime();
        while(~scanf("%d",&n)&&n)
        {
            int m=n;
            while(m++)
            {
                if(isprime(m)) continue;//这个数还不能是素数 
                int ans1=f(m);
                int ans2=cnt(m);
                if(ans1==ans2)
                {
                    printf("%d\n",m);
                    break;
                }
            }
    
        }
        return 0;
    }