Numéro Smith, erreur de délai d'attente pour l'optimisation des grandes entrées

Question

J'ai écrit ce code pour vérifier si un non est smith non ou pas sur hackerrank. Un nombre de Smith est un nombre composé, dont la somme des chiffres est la somme des chiffres de ses facteurs premiers obtenus à la suite de la factorisation en nombres premiers (excluant). Les premiers nombres sont 4,22,27. Ce code fonctionne parfaitement, mais donne l'erreur délai d'attente pour l'entrée = 2050918644. Maintenant, pouvez-vous me dire comment puis-je modifier ce code et assurez-vous qu'il ne marche pas me donner l'erreur de délai d'attente

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

Vous ne devez pas boucle tout le chemin de 2 à x. Dans le pire des cas, votre numéro est some prime number * 2, donc vous couvrirez tous les facteurs premiers faisant la moitié du travail (puisque le nombre premier lui-même ne peut pas être le nombre de Smith). Ainsi, votre boucle for ressemblera à ceci:

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

Cela fonctionne beaucoup plus rapide et peut ou peut ne pas être suffisant pour vous, mais c'est loin d'être optimale. Si vous avez besoin de quelque chose plus rapide, s'il vous plaît lire sur des algorithmes principaux de factorisation à l'aide de tamis, Pollard algorithme de rho etc.

Notez également que si vous souhaitez utiliser un plus grand nombre que 2^31-1, vous devez utiliser autre chose que int (au moins long) .