M3.1011 PyGame[3]

Non prima di venerdì sera …

Sappiamo che i fattori primi di 13195 sono 5,7,13 e 29.

Quale è il più grande fattore primo di 600851475143 ?

 

valore: 2 crediti

 

Questa voce è stata pubblicata in Algoritmi, Informatica, M3, M3.1011 e contrassegnata con , . Contrassegna il permalink.

28 risposte a M3.1011 PyGame[3]

  1. Edoardo Bastianetto ha detto:

    Ho postato su dropbox, un altro modo per risolverlo per partecipare all’ ottimizzazione

    • bobcarr ha detto:

      interessante soluzione; molto efficiente per la soluzione del problema (47 millisec contro i 600 e passa di ahmed)

      rilevo una stranezza: se provo con il numero 72341, il tuo programma impiega 787 millisec, mentre quello di ahmed è istantaneo (0 millisec)
      chi mi spiega questo fatto (i 3 crediti)

      • Edoardo Bastianetto ha detto:

        M.. perchè 72341 è un numero primo, e trovando il programma di Kouza prima i fattori e poi i primi, deve controllare solo quel numero.
        Mentre il mio cerca prima i numeri primi e controlla dopo se sono fattori, e quindi perde molto tempo trovando numeri primi che alla fine non sono fattori.

        • bobcarr ha detto:

          si, la spiegazione è buona, però vorrei anche una conclusione; voglio dire: accertato questo fatto, quale morale devo trarre dalla cosa (per futuri problemi analoghi)

        • Edoardo Bastianetto ha detto:

          In questo caso i risultati validi ( i fattori primi ) solo l’intersezione di due insiemi, quello che contiene i numeri primi e quello che contiene i fattori.
          Dato che l’insieme dei fattori è più piccolo* conviene prima trovare gli elementi di questo; e poi controllare quali elementi di questo insieme sono presenti anche su quello dei primi.
          Più in generale conviene prima scoprire gli elementi dell’insieme più piccolo e dopo se sono presenti nell’insieme più grande, perché così abbiamo meno elementi da controllare.

        • bobcarr ha detto:

          mi viene im mente ora che, data la tua spiegazione, il programma di ahmed dovrebbe essere più veloce anche nel caso lungo, non ti pare?

        • Edoardo Bastianetto ha detto:

          Infatti credo il programma di Ahmed sia più lento perchè usa le liste.
          In teoria se sul mio cerco prima i fattori e poi controllo se sono primi dovrebbe metterci ancora meno, adesso provo.

        • Edoardo Bastianetto ha detto:

          Ok, adesso che il programma controlla prima i fattori con :
          72341 passa da circa 390 a 22 millisecondi
          600851475143 passa da circa 27 a 3 millisecondi
          =)

  2. bobcarr ha detto:

    invito tutti a dare un’occhiata al file che ho caricato in dropbox
    trattasi del programma di ahmed modificato per la valutazione del
    tempo di esecuzione
    può essere utile per verificare l’efficienza di un programma

  3. bobcarr ha detto:

    ok, ahmed vince (con aiuto edoardo, ma che volete, ormai ….)

    2 crediti

    restano 3 crediti per un programma migliore (se possibile)

  4. ahmed kouza ha detto:

    grazie al consiglio di bastianetto di mettere int ora viene scitto direttamente il risultato.. è nelle mia cartella su drop box sempre sotto il nome di pygame 3

  5. ahmed kouza ha detto:

    sono la lista dei numeri primi fino al numero dato ank a me viene così e ho messo il programma su drop box con il nome pygame 3k…

  6. Edoardo Bastianetto ha detto:

    71,839,1471,6857 quindi 6857 giusto ?

I commenti sono chiusi.