io sono arrivato alla soluzione (teorica) di monete complicate, (uno degli ultimi problemi quindi in prima pagina, anche se poi lunedì credo metteranno quelli della gara.
Il mio problema è la fattorizzazione in primi di un numero, e (magari stupidamente) mi chiedevo se esistesse un metodo più efficiente di 2 (3) cicli for annidati. Ok, la verifica se un numero n è o meno primo si può sempre ottimizzare invece che in O(n) in O(sqrt(n)) . Questo lo chiedo perché ho visto che le soluzioni migliori hanno tempi irrisori, 0,003s.
C’è la possibilità che mi sia sbagliato completamente sulla soluzione, quindi ditemi se è giusta quella che ho pensato.
La soluzione al problema è (in tutti i casi) la somma degli esponenti dei fattori primi +1 (perché un fattore è l’uno, se si vuole). Vale a dire, se il numero è 60 = 223*5, allora la soluzione è 5?
La soluzione che hai pensato è corretta. Per poter trovare la fattorizzazione si può usare anche solo un ciclo. Prova a pensare al questo ciclo, partendo con il numero 2: se il numero è un divisore cosa faccio? E se non lo fosse?
si vero ho pensato che la fattorizzazione si poteva in qualche modo ottimizzare. Però ad onor del vero lo ho codificato diciamo con l’algoritmo “meno peggio”, cioè con l’idea generale, in termini di cicli, non ottimizzata (ogni ciclo per trovare un fattore riparte ogni volta da capo, non dal fattore precedente) MA i cicli sono tutti ottimizzati alla radice quadrata. Però gira nello stesso tempo degli altri (e fa 100 punti)… quindi alla fine mi chiedo, e a sto punto diventa pura curiosità personale, input troppo piccolo o server troppo potente ?
?