Главный генератор PRIME1 на SPOJ - PullRequest
Новая
       89

Главный генератор PRIME1 на SPOJ

0 голосов
/ 29 августа 2018

Питер хочет сгенерировать некоторые простые числа для своей криптосистемы. Помоги ему! Ваша задача - сгенерировать все простые числа между двумя заданными числами! Входные

Ввод начинается с числа t тестовых случаев в одной строке (t <= 10). В каждой из следующих t строк есть два числа m и n (1 <= m <= n <= 1000000000, n-m <= 100000), разделенные пробелом. Выход </p>

Для каждого теста выведите все простые числа p, такие что m <= p <= n, по одному на строку, тесты, разделенные пустой строкой. </p>

Может ли кто-нибудь помочь мне оптимизировать мой код, поскольку он показывает превышение лимита времени даже после того, как я использую sieve. Вот ссылка на проблему https://www.spoj.com/problems/PRIME1/ Вот мой код: 

#include <iostream>
#include <math.h>
using namespace std;

int is_prime(int m)
{
    int i,c=0;
    for(i=2;i<=sqrt(m);i++)
    {
        if(m%i==0)
        c++;
    }

    if(c==0)
    return 1;
    else
    return 0;
}
int main()
{
    int n,m,i,j,k,num;
    cin>>num;
    for(i=1;i<=num;i++)
    {
      cin>>m>>n;


      int a[n];
      for(j=0;j<=n;j++)
      a[j]=1;
      for(j=m;j<sqrt(n);j++)
      {
         if(is_prime(j)==1)
         {

            for(k=j*j;k<=n;k=k+j)
            {
                a[k]=0;
            }
         }
      }
      for(j=m;j<=n;j++)
      {
            if(a[j]==1)
            cout<<j<<endl;


      }
    cout<<endl;


   }

    enter code here
    return 0;
}

1 Ответ

0 голосов
/ 29 августа 2018

Ваш код имеет несколько проблем:

  • Вы не можете создать массив 10 ^ 9 (int a[n]) в данное ограничение по времени!

  • Вложенные для циклов занимают слишком много времени почти O(sqrt(n-m)^2)

Для оптимизации используйте https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes и https://www.geeksforgeeks.org/segmented-sieve/

...