Trova la somma dei multipli di 3 o 5, minore di 1.000.000

Modifica al Project Euler.

« Older   Newer »
 
  Share  
.
  1. Wextum
     
    .

    User deleted


    CODICE
    >>> print sum(range(0,999999,3 or 5))
    166665833334


    Ehm, no.. :)
     
    Top
    .
  2. lumo
     
    .

    User deleted


    CITAZIONE (RootkitNeo @ 19/4/2012, 23:11) 
    @lumo: anche in un int ci sta comunque. Ovvio, se viene inserito un numero un poco più grande, esce dal range e diventa negativo.

    Ripeto la soluzione per i meno attenti: 1404932684

    Se ciò che dici fosse vero, allora cambiando gli int in long long int nel tuo codice non cambierebbe nulla. Invece se lo faccio viene fuori il risultato che ho ottenuto ( provare per credere ).
    A ulteriore prova, se ancora non fossi convinto, considera 233333166668.
    Questo numero è dato dalla somma (2^31)*108 + 1404932684.
    E questo vuol dire che il tuo integer va in overflow un bel po' di volte :)
     
    Top
    .
  3.  
    .
    Avatar

    Senior Member

    Group
    Staff
    Posts
    10,796

    Status
    Anonymous
    Devi ricordarti di togliere i multipli di 15 comunque.

    @lumo: ti ho risposto così convinto perchè il codice l'avevo scritto per risolvere l'altro, sino al 1000. Ora che mi ricordi invece il dettaglio della modifica, noto che hai senza dubbio ragione. Chiedo venia. ;)
    Lo modificherò domani.
     
    Top
    .
  4. lumo
     
    .

    User deleted


    CITAZIONE (Wextum @ 19/4/2012, 23:30) 
    CODICE
    >>> print sum(range(0,999999,3 or 5))
    166665833334


    Ehm, no.. :)

    Senti se scrivi codice bovinamente senza nemmeno ragionarci non so cosa farci asd.
    La cosa che hai scritto non ha minimamente senso, infatti 3 or 5 dà come risultato 3, quindi quello che hai fatto non è altro che calcolare la somma dei multipli di 3 fino a 999999.

    Provo a fare un po' di chiarezza.
    Prendiamo tutti i multipli di tre. Questi sono nella forma:
    CODICE
    0, 3, 6, 9, ..., 3n

    Se consideriamo la somma di questi, possiamo trascurare lo zero e raccogliere il 3 a fattor comune, ottenendo.
    CODICE
    3( 1+2+3+4+...+n )

    A questo punto possiamo calcolare la sommatoria interna con un ciclo( sum(range(1,n+1)) ), oppure utilizzando la formula n*(n+1)/2.

    Lo stesso procedimento si applica per i multipli di 5.
    Ora però, per poter calcolare la somma dei multipli di 3 o 5, dobbiamo tener conto del fatto che il 15 è sia multiplo di 3 che di 5, e quindi è stato calcolato due volte nella somma.
    Quindi dobbiamo togliere tutti i multpli di 15( e più in generale, tutti i multipli di mcm(a,b) ).
     
    Top
    .
  5.  
    .
    Avatar

    Senior Member

    Group
    Staff
    Posts
    10,796

    Status
    Anonymous
    Non ho detto nulla riguardo a quell' 3 or 5 perchè avevo il dubbio se fosse considrato un or logico oppure bit a bit (e non conoscendo il linguaggio, ho preferito evitare).


    [inizio_delirio]
    Un tempo te lo dicevo lumo: quando partecipi ad una discussione oltre che ad innalzare il livello di conoscenza aumenti anche le visite. Guardare il contatore per credere, sono già 115.
    [fine_delirio]
     
    Top
    .
  6. massimop1973
     
    .

    User deleted


    Ecco, (tardivamente) la mia soluzione in Java

    CODICE
    import java.math.BigInteger;

    public class Problem1terzasoluzione
    {

           public static void main(String[] args)
           {        
                   BigInteger total = new BigInteger("0");
                   String numero;
           
                   for (long i = 1; i < 1000000L; i++)
                   {
                           if (i % 3 == 0 || i % 5 == 0)
                           {
                                   numero = i + "";
                                   total = total.add(new BigInteger(numero));
                           }
                   }
           
                   System.out.println(total);
           }
    }
     
    Top
    .
  7.  
    .
    Avatar

    Senior Member

    Group
    Staff
    Posts
    10,796

    Status
    Anonymous
    E' un po' troppo brute force però.
     
    Top
    .
  8. massimop1973
     
    .

    User deleted


    E non hai visto il primo programma che avevo scritto, per carità funzionava ma non era brute force ma idiot force
     
    Top
    .
  9. CaMpIoN
     
    .

    User deleted


    Forse l'argomento è vecchio, ma posto comunque per partecipazione :), la teoria utilizzata è la stessa spiegata da lumo, codice java:

    CODICE
    public class sumOfMultiples {
           public static long mSum(long max) {
                   return 3*ep1k1((long) ((max-1)/3))+5*ep1k1((long) ((max-1)/5))-15*ep1k1((long) ((max-1)/15));
           }
           public static long ep1k1(long n) {
                   return n*(n+1)/2;
           }
           public static void main(String[] args) {
                   System.out.println(mSum(1000000));
           }
    }
     
    Top
    .
23 replies since 18/4/2012, 15:08   785 views
  Share  
.