Aidez à exécuter ce code plus rapidement pour SPOJ

Question

J'ai fait quelques-uns des défis sur le Sphere Online Judge (SPOJ), mais je n'arrive pas à obtenir the second problem (le générateur principal) pour s'exécuter dans le délai imparti. Comment peut-on augmenter la vitesse du code suivant?

#include <stdio.h> 
#include <math.h> 

int is_prime(int n); 
void make_sieve(); 
void fast_prime(int n); 

int primes[16000]; 

int main() 
{ 
    int nlines; 
    int m, n; 
    make_sieve(); 
    scanf("%d", &nlines); 
    for (; nlines >= 1; nlines--) { 
     scanf("%d %d", &m, &n); 
     if (!(m % 2)) { 
      m++; 
     } 
     for (; m < n; m+=2) { 
      fast_prime(m); 
     } 
     printf("\n"); 
    } 
    return 0; 
} 

/* Prints a number if it's prime. */ 
inline void fast_prime(int n) 
{ 
    int j; 
    for (int i = 0; ((j = primes[i]) > -1); i++) { 
     if (!(n % j)) { 
      return; 
     } 
    } 
    printf("%d\n", n); 
} 

/* Create an array listing prime numbers. */ 
void make_sieve() 
{ 
    int j = 0; 
    for (int i = 0; i < 16000; i++) { 
     primes[i] = -1; 
    } 
    for (int i = 2; i < 32000; i++) { 
     if (i % 2) { 
      if (is_prime(i)) { 
       primes[j] = i; 
       j++; 
      } 
     } 
    } 
    return; 
} 

/* Test if a number is prime. Return 1 if prime. Return 0 if not. */ 
int is_prime(int n) 
{ 
    int rootofn; 
    rootofn = sqrt(n); 
    if ((n <= 2) || (n == 3) || (n == 5) || (n == 7)) { 
     return 1; 
    } 
    if (((n % 2) == 0) || ((n % 3) == 0) || ((n % 5) == 0) || ((n % 7) == 0)) { 
     return 0; 
    } 
    for (int i = 11; i < rootofn; i += 2) { 
     if ((n % i) == 0) { 
      return 0; 
     } 
    } 
    return 1; 
} 

Answer 1

Actuellement, votre problème n'est pas une limite de temps. C'est le fait que votre programme n'imprime jamais de nombres.

L'erreur la plus évidente est que dans fast_prime vous vérifiez si n est divisible par le premier [0], le premier [1], ... jusqu'au premier [k]. Même si n est premier, vous ne l'imprimerez pas, car n est quelque part dans primes [], et donc vous obtiendrez que n est divisible par un certain nombre ...

Pour corriger cela, vous devez vérifier que n est divisible par un nombre premier jusqu'à la racine carrée de n (cela aura aussi l'effet secondaire d'accélérer le code, car moins de nombres seront vérifiés avant de décider qu'un nombre est un nombre premier)

changer fast_prime pour

inline void fast_prime(int n) 
{  
    int j; 
    int rootofn; 
    rootofn = sqrt(n);   
    for (int i = 0; ((j = primes[i]) > -1) && (j<rootofn); i++) { 
     if (!(n % j)) { 
      return; 
     } 
    } 
    printf("%d\n", n); 
} 

Answer 2

isprime() n'utilise pas la table des nombres premiers nombres []. De plus, implémentez une recherche du tableau des primes qui se terminera rapidement en utilisant un algorithme de recherche binaire. La bibliothèque standard en a un.

Pour voir où votre temps est consacré dans le code que vous pouvez utiliser le profilage exemple gcc

gcc -p -g - o mycode mycode.c 
===run the code-- 
gprof mycode