Помогите заставить этот код работать быстрее для SPOJ - PullRequest
Новая
       7

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

0 голосов
/ 29 мая 2010

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

#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;
}

Ответы [ 2 ]

2 голосов
/ 29 мая 2010

isprime () не использует простые числа таблицы простых чисел [].

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

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

gcc -p -g - o mycode mycode.c
===run the code--
gprof mycode
1 голос
/ 29 мая 2010

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

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

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

изменить fast_prime на 

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);
}
...