Qual è un buon risultato in termini di tempo?

Question

Ho notato che molti hanno tempi di esecuzioni veramente molto bassi. Io sono partito da 14 secondi e sono sceso a 2, ma molti hanno anche 4ms. Ovviamente il problema è sui numeri grandi, il mio programma scompone il numero in fattori primi e ovviamente si ferma se ha già trovato k divisori. Li trova dividendo il numero per un numero che parte da 2 e poi diventa 2*n+1 con n che incrementa ogni volta. In questo modo genero tutti i primi che mi servono per effettuare la divisione e anche qualche composto. Nonostante questo non scendo sotto i 2 secondi, mi interessava sapere come avete fatto voi e  se 2 secondi è più che accettabile. Grazie.

Answer 1

Ciao, un consiglio è quello di sfruttare la radice quadrata, è spesso usata per cercare i numeri primi. Ti spiego brevemente il funzionamento, anche se su Internet trovi molte più informazioni spiegate meglio: prendi il numero 15, la radice quadrata approssimata per difetto è 3. Ora comincia il famoso ciclo, e fermalo quando arrivi a 3 (compreso). Vedrai che il 15 non è divisibile per 2, però lo è per 3 (infatti 15 / 3 fa 5). Ora sai che 3 è un divisore di 15, ma anche 15/3, ossia 5, è un divisore di 15.

Comments

Non diciamo troppo, un pochino di pepe e di sana competizione deve restare :)
Comunque Alessio... Se capisci come implementare bene quello che hai detto sulla radice quadrata, è esattamente quello che bisogna fare :)

---

Chiedo scusa x ignoranza innanzitutto. Il mio primo esercizio risponde a tutti e 3 test in un tempo inferiore ai 30 secondi però nella pagina di risultati vedo 5334 MS x il primo esercizio! Ma questo che vuol dire? Visto che avete scritto 2 secondi posso sapere a cosa si riferisce? Il mio programma ci mette circa 12 secondi in totale.

---

2 secondi è il tempo che ci mette il mio programma a svolgere tutte le istruzioni per i valori dati dal tester, espresso in ms 2000 (ms=millisecondi, nb non voglio insultare esplicitandolo è solo per togliere qualsiasi dubbio, sui risultati globali è tutto espresso in ms). Quindi da come dici tu mi sembra di capire che il tuo programma dell'es 1 ci mette 5334ms ovvero 5, 3 secondi. Il 12 mi viene da pensare che l'elaboratore che esegue i testi sul sito sia più potente del tuo, oppure sia la somma dei tempi di tutte e tre i programmi.

Answer 2

Suggerimento: Radice quadrata :P
Non ti dico di più altrimenti ti tolgo il gusto della scoperta :D
Internet è il tuo migliore amico su questo :)

Comments

Io per esempio ho un tempo che varia da 1,20 a 1,70 ms sull'esercizio 1, ma non riesco ad abbassare ulteriormente il mio tempo di 0,5 (circa) ms sul 3°, quando c'è gente che lo fa in (circa) 0,1 ms :P

---

Quoto il suggerimento sulla radice quadrata

---

Radice quadrata così non capisco a cosa vi riferiate. Posso pensare che non serva dividere per numeri più grandi della radice quadrata. Ma non è vero, ad esempio 15 la sua radice è circa 3.87 e 5 è un suo divisore .