Fattorizzazione

Correttore online – Facili

È dato il numero intero x.
Si deve rappresentare tale numero come prodotto di due numeri interi a e b (x=a*b) scelti in modo tale che sia massima la somma delle cifre che li compongono.

Dati di input

L’unica riga del file di input contiene il numero intero x (2 <= x <=10⁹).

Dati di output

Il valore massimo della somma delle cifre dei numeri a e b.

Esempi di input/output

input.txt	output.txt
6	7
10	7

Autore/i: A.S. Stankevich, ACM ICPC Team St. Petersburg State University of Information technology, Mechanics and Optics.

/*
    www.valcon.it
	OII - Esercizi facili - Fattorizzazione
*/

#include 
#include 
#include 
using namespace std;

int cifre(long n)
{
	int tot=0;
	while(n > 0)
	{
		tot += n%10;
		n    = n/10;
	}
	return tot;
}

int main()
{
	ifstream fin ( "input.txt");
	ofstream fout("output.txt");
	
	long x, a,b;
	int  max, somma;	
	
	fin >> x;		
	double rx=sqrt(x);
	max=0;
    for(a=1; a <= rx; a++)	
	{
		if(x%a == 0)
		{
			b=x/a;
			somma=cifre(a)+cifre(b);
			if(somma > max)
			    max=somma;
    	}
    }  
	fout << max;
	return 0;
}