スミス番号、大きな入力のタイムアウトエラー

Question

このコードは、noがsmack noであるかどうか、またはhackerrankにないかどうかをチェックするために書かれています。 スミス数は合成数です。その桁の合計は、素因数分解（除外）の結果として得られた素数の桁の合計です。最初の数は4,22,27です。 このコードは完璧に動作しますが、入力のタイムアウトエラーが発生します= 2050918644. は今、あなたはどのように私はこのコードを編集し、あなたがする必要はありません、それは私にタイムアウトエラー

import java.io.*; 
import java.util.*; 

public class Solution { 
static int sumD(int a){ 
     int sum=0; 
    while(a>0) 
    { 
     int rem=0; 
     rem=a%10; 
     sum=sum+rem; 
     a=a/10; 


    } 
    return sum;} 
    public static void main(String[] args) { 
     /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ 
    Scanner sc=new Scanner(System.in); 
     int x=sc.nextInt(); 
     int s=0; 
     int temp=x; 
     for(int i=2;i<x;i++) 
     { 
      while(temp%i==0) 
      { s=s+ sumD(i); 
      temp=temp/i;} 
     } 
     if(sumD(x)==s) 
      { 
      System.out.println(1); 

     } 
     else 
      System.out.println(0); 
     } 

} 

Answer 1

を与えるdoesntのことを確認することができます私に言うことができます2からxまでの途中でループします。最悪のシナリオでは、番号はsome prime number * 2なので、仕事の半分を行うすべての素因数をカバーします（素数自体はスミス番号ではないため）。だからあなたのforループは次のようになります。

は

for(int i=2;i<=x/2;i++) 
{ 
    while(temp%i == 0){ 
     s=s+ sumD(i); 
     temp=temp/i; 
    } 
} 

これは、はるかに高速に動作し、またはあなたのために十分であってもなくてもよい、しかしこれが最適には程遠いです。あなたがより速く、何かが必要な場合は、ふるいを使用して素因数分解アルゴリズムについてお読みください、ポラードのrhoアルゴリズムなど

また、あなたが2^31-1よりも高い数値を使用したい場合は、あなたがintよりも何か他のものを使用する必要があることに注意してください（少なくともlong） 。