Domanda Problema con il tempo di esecuzione di un programma.

[Justsniper92]

Ciao ragazzi, ho un problema con questo codice, il testo dice:

"Scrivere un codice in C che generi un insieme di numeri random. Si generino tanti numeri in modo tale che sia possibile selezionare da questo set esattamente (e soltanto) 50 numeri primi. Successivamente si ordini il sottoinsieme di 50 numeri primi in ordine decrescente".

Sono riuscito a scrivere il codice, il problema è che ci mette molto tempo per eseguirlo : circa 4 minuti, c'è un modo per renderlo più veloce?

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 50

int main() {

      int i;
      int j;
      int k;
      int A[N] ;
      int B;
      int cont;
      int div;
      int temp;
    
      div=cont=0;
      k=0;
    
      srand(time(NULL));
    
//GENERAZIONE NUMERI 
 
      do {
            B = rand ()  ;
            for(j=1;j<=B;j++){
                  if(B%j==0)
                        div=div+1;
                              if(div>2)
                                    break;
             }               
      if (div==2){
            printf("%d\n",B);
                  cont=cont+1;
                        A[k++]=B;
      }         
      div=0;         
      }
      while(cont!=N);
 
//ORDINAMENTO NUMERI PRIMI
    
     for(i=0;i<N;i++)
            for(j=0;j<N;j++){
                  if( A[j] < A[i] ){
                  temp = A[i];
                  A[i] = A[j];
                  A[j] = temp;
                  }
            }                 

      for (i = 0; i < N ; i++) {
            printf("\nIl %d° numero primo è : %d ",N-i,A[i]);
      }
}

 

[St3ve]

Invece che controllare se B ha esattamente due divisori, puoi controllare se B ha almeno un divisore maggiore di 1 e inferiore o uguale alla radice quadrata di B. Piuttosto che calcolare esplicitamente la radice quadrata, puoi usare un ciclo di questo tipo: for(int j = 2; j * j <= B; j++){ /* something */ }.

Si può migliorare ulteriormente il codice, ma già dopo questa piccola modifica il tuo programma dovrebbe terminare in meno di un secondo. Dopo che avrai provato a sistemare il codice autonomamente ti faccio vedere come lo farei io.

EDIT: Anche l'algoritmo di ordinamento è sbagliato, controlla da dove parte il for interno.

 

[Super Squirrel]

puoi usare un ciclo di questo tipo: for(int j = 2; j * j <= B; j++){ /* something */ }.

Io invece farei qualcosa del genere:

for(n = rand(), flag = i = 2; i <= n / i && (flag = n % i); i += i == 2 ? 1 : 2);

In questo modo si elimina il rischio di overflow dovuto a j * j e inoltre possiamo dire che la divisione è quasi a costo zero visto che dopo va comunque utilizzato l'operatore modulo sugli stessi operandi.