Помогите сделать этот код более быстрым для SPOJ

Question

Я выполнял несколько задач на Sphere Online Judge (SPOJ), но я не могу заставить the second problem (генератор первичных чисел) работать в течение срока. Как увеличить скорость следующего кода?

#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

В настоящее время проблема заключается не в ограничении времени. Это факт, что ваша программа никогда не печатает никаких чисел.

Наиболее очевидной ошибкой является то, что в fast_prime вы проверяете, делится ли n на простые [0], prime [1], ... до простого [k]. Даже если n является простым, вы не будете его печатать, потому что n находится где-то в простых [], и поэтому вы получите, что n делится на некоторое число ...

Для исправления этого вопроса вам необходимо проверить что n делится на некоторое простое число до квадратного корня из n (это также будет иметь побочный эффект от ускорения кода, поскольку меньшее количество номеров будет проверено до того, как будет принято какое-либо число).

change fast_prime to

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() не использует таблицу простых чисел простых чисел [].

Плюс, реализуйте поиск массива простых чисел, который будет быстро завершен с использованием алгоритма бинарного поиска. В стандартной библиотеке есть одна.

Чтобы увидеть, где ваше время тратится на код, который вы можете использовать профилирование НКУ пример

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