хакерранк первичных подстрок Рамануджана 1 проблема - PullRequest
Новая
       83

хакерранк первичных подстрок Рамануджана 1 проблема

0 голосов
/ 28 марта 2020

Вопрос в следующем:

Рамануджан так любит играть в числовые игры. Однажды Рамануджан и Ани sh сыграли в игру. Рамануджан дал Ани sh числовую строку и попросил его найти все различные подстроки размером не более шести, которые являются простыми. Ани sh, хорошо разбирающаяся в математике, берет игру на себя, и если он может дать решения для всех входных наборов, которые ему предоставляет Рамануджан, Ани sh выигрывает игру. Ваша задача помочь Ани sh выиграть игру.

Формат ввода

Первая строка содержит T, Количество тестовых случаев. Каждый тестовый пример содержит строку размера N, содержащую только целые числа.

Ограничения

1 <= Количество тестовых случаев <= 10 1 <= N <= 10 ^ 7 </p>

Выходной формат

Для каждого тестового примера выведите общее количество различных простых подстрок длины не более 6.

Мой код написан на c ++: я создал вектор и карту всех простое число, которое меньше квадрата root из 10 ^ 7 и имеет инициализированную карту с 1 (1 обозначает простое число, 0 обозначает составное число). Даже для проверки, является ли число простым или нет, я делю его только на простое число, меньшее его квадрата root. Но даже делая все это, я не могу пройти 2-й тестовый случай (показывающий завершение из-за тайм-аута). Я могу только пройти 1-й тестовый случай. Я думаю, что моя программа тратит много времени на создание подстрок (используя функцию substr () Есть ли способ уменьшить сложность времени? Ответ PLZ. 

map<long int,int>mp{{2,1},{3,1},{5,1},............................,{3121,1},{3137,1}};


map<long int,int>p;

vector<long int>v{2,3,5,..............3137};

 long int c=0;


void check_prime(long int n)

{
    long int i;



     int flag=-1;

        for(i=0;v[i]*v[i]<=n;i++)
        {

            if(n%v[i]==0)
            {
                flag=1;
                break;
            }

        }
        if(flag==-1)
        {
            ++c;
            mp.insert(pair<long int,int>(n,1));


            p.insert(pair<long int,int>(n,1));


        }
        else
        {
            mp.insert(pair<long int,int>(n,0));
            p.insert(pair<long int,int>(n,1));
        }




}
int main() {


    int t;
    string s;
    long int  n,n1,i,j;

    cin>>t;
    while(t--)
    {
        long int i,j;

        cin>>s;


        for(i=0;i<s.length();i++)
        {
             int l=s.length()-i;

            for(j=1;j<=min(6,l);j++)
            {
                n=stoi(s.substr(i,j));



              if(p.count(n)==0)  
              {
                if(mp.count(n)==1 )
                {
                    if(mp[n]==1 )
                    {
                        ++c;
                        p.insert(pair<long int,int>(n,1));

                    }
                    else
                    {
                         p.insert(pair<long int,int>(n,1));
                    }
                }
                else
                {
                   if(n<3162 || n%2==0 || n%5==0)
                   {
                       mp.insert(pair<long int,int>(n,0));
                       p.insert(pair<long int,int>(n,1));
                   }

                    else
                    {

                       check_prime(n);
                    }

                }
              }
            }
        }
        cout<<c<<endl;
        p.clear();
        c=0;
    }
    return 0;
}

1 Ответ

0 голосов
/ 28 марта 2020

Вам не нужно каждый раз вызывать check_prime() в l oop.

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

Рассмотрим сито Эратосфена: 

int np[1000000];  // not prime
int main(void)
{
    np[1] = 1;
    for (int i = 2; i*i < 1000000; i++)
        for (int j = 2; i*j < 1000000; j++)
            np[i*j] = 1;

    // use np[n].
    return 0;
}

При использовании np[n] потребуется O(1) в отличие от O(sqrt(n)) ранее.

...