Мое сито Эратосфена занимает слишком много времени

Question

Я реализовал Сито Эратосфена для решения проблемы SPOJ PRIME1 .Хотя вывод в порядке, мое представление превышает ограничение по времени.Как я могу сократить время выполнения?

int main()
{
  vector<int> prime_list;
  prime_list.push_back(2);
  vector<int>::iterator c;
  bool flag=true;
  unsigned int m,n;
  for(int i=3; i<=32000;i+=2)
  {
    flag=true;
    float s = sqrt(static_cast<float>(i));
    for(c=prime_list.begin();c<=prime_list.end();c++)
    {
        if(*c>s)
            break;
        if(i%(*c)==0)
        {
            flag=false;
            break;
        }
    }
    if(flag==true)
    {
        prime_list.push_back(i);
    }
  }
  int t;
  cin>>t;
  for (int times = 0; times < t; times++)
  {
    cin>> m >> n;
    if (t) cout << endl;
    if (m < 2)
        m=2;
    unsigned int j;
    vector<unsigned int> req_list;
    for(j=m;j<=n;j++)
    {
        req_list.push_back(j);
    }
    vector<unsigned int>::iterator k;
    flag=true;
    int p=0;
    for(j=m;j<=n;j++)
    {
        flag=true;
        float s = sqrt(static_cast<float>(j));
        for(c=prime_list.begin();c<=prime_list.end();c++)
        {
            if((*c)!=j)
            {
                if((*c)>s)
                    break;
                if(j%(*c)==0)
                {
                    flag=false;
                    break;
                }
            }
        }
        if(flag==false)
        {
            req_list.erase (req_list.begin()+p);
            p--;
        }
        p++;
    }
    for(k=req_list.begin();k<req_list.end();k++)
    {
        cout<<*k;
        cout<<endl;
    }
  }
}

Answer 1

Ваш код работает медленно, потому что вы не реализовали алгоритм Sieve of Eratosthenes.Алгоритм работает следующим образом:

1) Create an array with size n-1, representing the numbers 2 to n, filling it with boolean values true (true means that the number is prime; do not forget we start counting from number 2 i.e. array[0] is the number 2)
2) Initialize array[0] = false.
3) Current_number = 2;
3) Iterate through the array by increasing the index by Current_number.
4) Search for the first number (except index 0) with true value.
5) Current_number = index + 2;
6) Continue steps 3-5 until search is finished.

Этот алгоритм занимает O (nloglogn) время.То, что вы делаете, на самом деле занимает гораздо больше времени (O (n ^ 2)).Кстати, на втором шаге (где вы ищете простые числа между n и m) вам не нужно проверять, являются ли эти числа снова простыми, в идеале вы должны рассчитать их на первом этапе алгоритма.

Как я вижу на сайте, который вы связали, основная проблема заключается в том, что вы не можете создать массив размером n-1, поскольку максимальное число n равно 10 ^ 9, что вызывает проблемы с памятью, если вы делаете это таким наивным способом.Это ваша проблема:)

Answer 2

Я бы выбросил то, что у вас есть, и начал бы с действительно простой реализации решета, и добавил бы больше сложности, только если это действительно необходимо.Вот возможная отправная точка:

#include <vector>
#include <iostream>

int main() {
    int number = 32000;
    std::vector<bool> sieve(number,false);
    sieve[0] = true;  // Not used for now, 
    sieve[1] = true;  //   but you'll probably need these later.

    for(int i = 2; i<number; i++) {
        if(!sieve[i]) {
            std::cout << "\t" << i;
            for (int temp = 2*i; temp<number; temp += i)
                sieve[temp] = true;
        }
    }
    return 0;
}

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

Answer 3

Я не совсем уверен, что вы внедрили сито Erasthotenes.В любом случае, пара вещей, которые могли бы в некоторой степени ускорить ваш алгоритм, будут: Избегать многократного перемещения векторного содержимого путем предварительного выделения пространства (поиск std::vector<>::reserve).Операция sqrt стоит дорого, и вы, вероятно, можете полностью ее избежать, изменив тесты (остановитесь, когда x*x > y вместо проверки x < sqrt(y).

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

Обратите внимание, что сито не выполняет никаких операций для проверки, является ли число простым, если оно не было отброшено ранее, то оно является простым. Каждое не простое число посещаетсятолько один раз для каждого уникального фактора. С другой стороны, ваш алгоритм обрабатывает каждое число много раз (против существующих простых чисел)

Answer 4

Как я понимаю, проблема в том, что вы должны генерировать все простые числа в диапазоне [m, n].

Способ сделать это без необходимости вычислять все простые числа из [0, n], потому что это, скорее всего, замедляет вас, - сначала сгенерировать все простые числа в диапазоне [0, sqrt (n)].

Затем используйте результат для просеивания в диапазоне [m, n]. Чтобы сгенерировать начальный список простых чисел, реализуйте базовую версию решета Эратосфена (в основном просто наивная реализация из псевдокода в статье в Википедии).

Это позволит вам решить проблему за очень короткое время.

Вот простой пример реализации сита Эратосфена:

std::vector<unsigned> sieve( unsigned n ) {
    std::vector<bool> v( limit, true ); //Will be used for testing numbers
    std::vector<unsigned> p;            //Will hold the prime numbers

    for( unsigned i = 2; i < n; ++i ) {
        if( v[i] ) {                    //Found a prime number
            p.push_back(i);             //Stuff it into our list

            for( unsigned j = i + i; j < n; j += i ) {
                v[i] = false;           //Isn't a prime/Is composite
            }
        }
    }

    return p;
}

Возвращает вектор, содержащий только простые числа от 0 до n. Затем вы можете использовать это для реализации метода, который я упомянул. Теперь я не буду предоставлять реализацию для вас, но вам нужно сделать то же самое, что и в сите Эратосфена, но вместо использования всех целых чисел [2, n], вы просто используете результат, который вы нашли. Не уверен, что это слишком много?

Answer 5

Я думаю, что одним из способов немного ускорить ваше сито является предотвращение использования оператора мод в этой строке.

if(i%(*c)==0)

Вместо (относительно) дорогой операции мода,может быть, если вы итерировали вперёд в сите с добавлением.

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

Answer 6

Поскольку проблема SPOJ в первоначальном вопросе не указывает, что ее необходимо решить с помощью сита Эратосфена, вот альтернативное решение, основанное на эта статья .На моем шестилетнем ноутбуке он работает примерно за 15 мс для худшего одиночного теста (нм = 100 000).

#include <set>
#include <iostream>

using namespace std;

int gcd(int a, int b) {
   while (true) {
      a = a % b;

      if(a == 0)
         return b;

      b = b % a;

      if(b == 0)
         return a;
   }
}

/**
 * Here is Rowland's formula. We define a(1) = 7, and for n >= 2 we set 
 *
 * a(n) = a(n-1) + gcd(n,a(n-1)). 
 *
 * Here "gcd" means the greatest common divisor. So, for example, we find
 * a(2) = a(1) + gcd(2,7) = 8. The prime generator is then a(n) - a(n-1),
 * the so-called first differences of the original sequence.
 */
void find_primes(int start, int end, set<int>* primes) {
   int an;        // a(n)
   int anm1 = 7;  // a(n-1)
   int diff;

   for (int n = start; n < end; n++) {
      an = anm1 + gcd(n, anm1);

      diff = an - anm1;

      if (diff > 1)
         primes->insert(diff);

      anm1 = an;
   }
}

int main() {
   const int end = 100000;
   const int start = 2;

   set<int> primes;

   find_primes(start, end, &primes);
   ticks = GetTickCount() - ticks;

   cout << "Found " << primes.size() << " primes:" << endl;

   set<int>::iterator iter = primes.begin();
   for (; iter != primes.end(); ++iter)
      cout << *iter << endl;
}

Answer 7

Профилируйте свой код, найдите горячие точки, устраните их. Windows , Linux ссылки профилировщика.