Come posso eseguire "Milioni di calcoli?"

Question

Il mio codice è incollato di seguito. Quando eseguo questo programma, continua a calcolare. Sto utilizzando il vecchio compilatore Turbo C++. Quanto tempo dovrebbe impiegare per l'esecuzione di un programma del genere? Ho aspettato circa 5 minuti ma non c'era alcun output.

/*The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.
*/
#include<stdio.h>
#include<conio.h>
#define TWO_MILLION 2*1000*1000
int IsPrime(long unsigned int num);
int main()
{
    long unsigned int i,sum=0;
    clrscr();
    for(i=2;i<TWO_MILLION;i++)
    {
        if(IsPrime(i))
        sum+=i;
    }
    gotoxy(25,25);
    printf("%ld",sum);
    getch();
    return 0;
}
int IsPrime(long unsigned int num)
{
    int flag=1;
    long unsigned int i;
    for(i=2;i<num;i++)
    {
        if(num%i==0)
        {
            flag=0;
            break;
        }
    }
    return flag;
}

Answer 1

Non stanno facendo milioni di calcoli, si sta facendo bilioni di loro.

ISPrime sarà eseguito in O (n), che è esso deve svolgere 2 milioni di istruzioni solo per determinare quel singolo numero. Fare questo genere di cose tempo due milioni ci vorrà troppo tempo.

Per fare questo si vuole veramente usare qualcosa come: http://en.wikipedia.org/wiki / Sieve_of_Eratosthenes , che può determinare molto più modo efficiente tutti i numeri primi in un determinato intervallo.

Answer 2

  

Quanto tempo dovrebbe prendere un tale programma da eseguire?

Questo dipende completamente dalla piattaforma. Ho il sospetto che dal momento che si sta eseguendo ~ (due milioni) ^ 2 operazioni (~ 4000 miliardi) i calcoli, un tempo terribile.

Ci sono modi molto migliori per eseguire quello che stai facendo - per esempio per controllare il primo è sufficiente controllare per la radice quadrata del numero, non tutta la strada fino al numero stesso. Per non parlare v'è probabilmente una soluzione di programmazione dinamico che può farlo molto molto più veloce di quello.

Answer 3

Come altri hanno detto, ci vorrà molto tempo. Un approccio alternativo e interessante è il crivello di Eratostene. Si può leggere su di esso in:

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

In pratica si inizializza un array con i numeri 2 ... 2 milioni. Il numero più basso non ancora elaborati è primo. Poi, si rimuovono tutti i multipli di tale numero dalla matrice e continuare. Verrà eseguito molto più veloce di quello che hai.

Answer 4

Risposta fuori dal comune

gotoxy(25,25);

Esegui il tuo programma in modalità testo?Se la schermata di testo è solo 80 x 25, e se la venticinquesima riga è occlusa da altre cose, è probabile che non vedrai alcun cambiamento nella schermata di testo.

Answer 5

Come altri hanno detto: controllare i limiti della vostra implementazione

Se TurboC++ ha , tali limiti attuativi hanno un corrispondente macro definita in tale intestazione

#include <limits.h>
#include <stdio.h>
int main(void) {
    printf("int goes from %d to %d.\n", INT_MIN, INT_MAX);
    printf("long goes from %ld to %ld.\n", LONG_MIN, LONG_MAX);
    return 0;
}

Se non funziona è necessario "Calcola" i limiti da soli. Sto passando a unsigned perché non c'è nessun problema di overflow con loro, e ho solo bisogno di "calcolare" il limite superiore (il limite inferiore è 0)

#include <stdio.h>
int main(void) {
    unsigned u;
    unsigned long lu;

    u = -1; lu = -1;
    printf("unsigned ints go all the way to %u\n", u);
    printf("unsigned longs go all the way to %lu\n", lu);
    return 0;
}

---

Sul mio sistema, il 1 ° programma uscite

int goes from -2147483648 to 2147483647.
long goes from -9223372036854775808 to 9223372036854775807.

e le uscite 2 ° programma

unsigned ints go all the way to 4294967295
unsigned longs go all the way to 18446744073709551615

Answer 6

Ancora nessun commento / risposta circa la costante ad eccezione di un "epico" ...

#define TWO_MILLION 2*1000*1000

Questo è male. Quando si modifica il valore più tardi, si dispone di un nome-content-disadattamento:

#define TWO_MILLION 5*1000*1000

o si rinomina a

#define FIVE_MILLION 5*1000*1000

e necessità di cambiare ovunque avete usato. Non nominare le costanti dopo che il contenuto, questo solo trasforma i numeri magici in nomi magici. loro nome dopo il loro significato, per esempio MAX_NUMBER UPPER_LIMIT RANGE_TO_TEST o qualsiasi altra cosa si adatta meglio.

Answer 7

è possibile utilizzare metodi di crivello a fare anche questo, che non sono molto più complicate di quello che si sta utilizzando. L'idea è quella di raccogliere i primi n numeri primi consecutivi e li usa per costruire un setaccio. Discuto esso (con prove) in mia risposta ad un'altra domanda e Sheldon L. Cooper fornisce un'implementazione in sua . Non credo che ha ottenuto abbastanza upvotes per farlo (ho già preso 'bella risposta', quindi forse si poteva aiutarlo fuori su questo.

così dopo si calcolano i numeri setaccio, avete solo bisogno di test per la divisibilità per numeri che la linea con il setaccio e sono più piccoli rispetto alla radice quadrata di n.

Answer 8

Questo potrebbe richiedere un molto tempo per l'esecuzione.

Aggiungi questo per vedere i tuoi progressi (anche se ci vorrà ancora più tempo):

for(i=2;i<num;i++)
    {
        if(num%i==0)
        {
            flag=0;
            printf("%d,", num); /* <== show the prime */
            break;
        }
    }

Modifica

Come altri stanno sottolineando, questo è il modo più lento per contare i numeri primi. Forse lo scopo della vostra assegnazione è quello di ottenere a guardare in alto (e implementare) quelli più veloci?

Answer 9

I risultati del programma di integer overflow, è possibile utilizzare lungo tempo per risolvere il problema.

Inoltre, l'algoritmo per verificare se un numero è primo non è molto buona. Un altro modo che è altrettanto facile è quello di testare i numeri 2 alla radice quadrata del numero. Hai solo controlla fino alla radice quadrata del numero per determinare se è primo.

Answer 10

Un cambiamento semplice sarebbe mostrare quanto velocemente il vostro programma è in esecuzione, e quanto lavoro ha a che fare. E 'facile da stampare il vostro stato di circa ogni 100 iterazioni. (Oppure si potrebbe impostare a 1000 o 10000 iterazioni.)

---

Riconoscere che si potrebbe Doppio la velocità del vostro loop in IsPrime.
Dopo il check-2, avete solo bisogno di controllare i numeri dispari, e potrebbe avanzare con i+=2 invece di i++.

Se siete preoccupati per la velocità, perché stai spendendo così tanto tempo a controllare i numeri pari? (Nota che una volta che si inizia a fare solo i dispari-numeri, è inoltre necessario modificare il test di uscita per essere un numero dispari)

Puoi Doppio la velocità del ciclo in main così da evitare anche i numeri anche lì. (Ancora una volta, è necessario speciale-caso 2, quindi utilizzare i + = 2, a partire da 3 per ottenere 3, 5, 7, 9 ....)

Per rendere il ciclo in esecuzione IsPrime due volte più veloce, e rendendo il ciclo in esecuzione main due volte più veloce, questo dovrebbe rendere il vostro programma go 4X più veloce. (Se avrebbe preso un'ora prima, ora sarà di 15 minuti.)

---

L'altro miglioramento grande velocità si potrebbe fare solo è in esecuzione il ciclo per sqrt(num), invece di num

Poiché odio portando in funzioni di punto, come sqrt galleggiante, io invece consigliabile un approssimazione che si ferma entro 100 iterazioni passare il confine sqrt, e anche mostrare aggiornamenti di stato regolarmente.

if (num%2 == 0)
{
    flag=0;
    return flag;
}

/* Now that we checked 2, we only need to check odd numbers from now on. */
for(i=3;i<num;i+=2)
{
    if (i%101 == 0)
    {
        printf("i is %d out of %d\n", i, num);
        if (i*i > num)
        {
            break;  /* If you pass the sqrt boundary, quit. */
        }
    }

    if(num%i==0)
    {
        flag=0;
        break;
    }
}

---

P.S. Ho messo questo codice in un progetto C # (minore porting). Certo, questo è stato ora in esecuzione su un sistema operativo a 64 bit, con una migliore compilatore e 2.8GHz CPU.
Ha funzionato in meno di 20 secondi.