Il miglior divisore

Correttore online – Intermedi

Dati due interi positivi a e b, diciamo che a è migliore di b se la somma delle cifre decimali di a è maggiore di quella di b.

Per esempio, 119 è migliore di 512 perché 1+1+9 > 5+1+2.
Se le due somme sono uguali, allora a è migliore di b se a < b.
Per esempio, 119 è migliore di 191 perché 1+1+9=1+9+1 ma 119 < 191.

La nozione di migliore si può estendere in modo naturale a un insieme di interi: per esempio, il migliore tra 119, 191 e 512 è 119, in quanto quest’ultimo è migliore degli altri e non ce n’è nessuno migliore.

Dato un intero positivo n, un suo divisore è un intero d tale che la divisione di n per d fornisce resto nullo.

Per esempio, dato n=12, i suoi divisori sono 1, 2, 3, 4, 6 e 12 stesso (anche 1 e n sono da considerare fra i divisori di n).
Si noti che il migliore tra questi è 6 in quanto gli altri danno luogo a una somma di cifre inferiore a 6.

Scrivere un programma che riceve un intero positivo n e trova il migliore fra i suoi divisori.

Dati di input

Il file input.txt è composto da un’unica riga contenente un intero positivo n

• 1 ≤ n ≤ 10000.

Dati di output

Il file output.txt è composto da un’unica riga contenente l’intero che rappresenta il miglior divisore di n.

Esempi di input/output

input.txt	output.txt
10	5
239	239

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

/*
	www.valcon.it
	Correttore online - Intermedi - Il miglior divisore
*/

#include
#include
using namespace std;

int migliore_somma  =1,
    miglior_divisore=1; 		// output

void elabora(int n)
{
	int x=n;
	int s=0;
	
	while(x > 0)
	{
		s += x%10;
		x =  x/10;
	}
    
	if(s > migliore_somma) 
	{ 
	    migliore_somma  =s; 
		miglior_divisore=n; 
	}
}

int main()
{
	ifstream fin ( "input.txt");
	ofstream fout("output.txt");	
	int      n,          		// input
             divisore,        
             quoziente;                	
			 	
    fin >> n;    
    for(divisore=1; divisore <= n/2; divisore++)   
	{
    	if(n%divisore == 0)
    	{
    		quoziente=n/divisore;    		
    		elabora(divisore );
    		elabora(quoziente);
        }
	}
    
   	fout << miglior_divisore;
	return 0;
}