SPOJ Liczby znaczące - Przekroczono limit czasu

Question

Witam! Cały dzień męczę się z zadaniem ze spoja - https://pl.spoj.com/problems/PZPI3/ . Pomimo tego, że kod działa dobrze serwis cały czas wyrzuca "Przekroczono limit czasu". Czy ma ktoś jakiś pomysł na przyspieszenie algorytmu? Z góry dziękuję! 

int significant_numbers(int b, int e)
{
    int number = 6;
    int ans = 0;
    int buf = number * number;
    
    if (e >= 4 && 4 >= b)
    {
        ans++;
    }

    if (e >= 9 && 9 >= b)
    {
        ans++;
    }

    while (buf <= e && buf <= 1000000000)
    {
        int buffor = sqrt(number);
        buf = number * number;

        if (buf >= b)
        {
            for (int i = 3; i <= buffor + 1; i=i+2)
            {
                if ((number - 1) % i == 0)
                {
                    break;
                }

                if (i >= buffor)
                {
                    ans++;
                    break;
                }
            }


            for (int i = 3; i <= buffor+1; i=i+2)
            {
                if ((number + 1) % i == 0)
                {
                    break;
                }

                if (i >= buffor)
                {
                    ans++;
                    break;
                }
            }

            number += 6;
        }
        else
        {
            number += 6;
        }
    }

    return ans;
}

 

Comments

Mógłbyś wyjaśnić swój pomysł na rozwiązanie? Bo nie bardzo rozumiem co się dzieje w tym kodzie.

---

Jasne. Funkcja dostaje dwie zmienne. Początek i koniec przedziału. Funkcja ma za zadanie sprawdzić jakie liczby pierwsze podniesione do kwadratu należą do tego przedziału (tylko kwadraty liczb pierwszych spełniają wymagania z zadania). Pętla while sprawdza podzielność liczb szukanych specjalnym dla liczb pierwszych algorytmem (6*x+-1). Dzielniki są sprawdzane do momentu, w którym nie przekroczą pierwiastka z danej liczby.

Answer 1

Problem jest taki, że dla każdego testu od początku szukasz liczb pierwszych na danym przedziale. Dla danych a = 1, b = 1e9, Twój program sprawdziłby wszystkie liczby postaci 6n+-1 w przedziale [1, sqrt(1e9)]. Tych liczb może być jakoś sqrt(1e9)/6, a dodatkowo musisz sprawdzić w O(sqrt(x)) czy każda z tych liczb jest pierwsza. Złożoność jest wtedy równa jakoś O(sqrt(b)^2*t), gdzie t to ilość testów, a to jest zdecydowanie za wolne.

Lepiej by było gdybyś sitem znalazł wszystkie liczby pierwsze nie większe niż sqrt(1e9), następnie dla każdego testu, musisz tylko przejść po tych wszystkich liczbach pierwszych  i znaleźć te których kwadraty mieszą się w przedziale [a, b]. Liczb pierwszych mniejszych od sqrt(1e9) nie będzie wiecej niż 10^4, więc to powinno zmieścić się w limitach czasowych

Comments

Teraz wygląda to w następujący sposób. Niestety SPOJ nadal wywala "Przekroczono limit czasu". Nie wiem co jeszcze mógłbym poprawić. Oczywiście wszystkie wyniki są poprawne.

int bufor = 31623;

void prime_numbers(bool* chk)
{
    int ans = 0;

    for (int i = 0; i < bufor + 1; i++)
    {
        chk[i] = 0;
    }
    
    for (int i = 2; i * i < bufor; i++)
    {
        for(int j = i * i; j <= bufor; j+=i)
            chk[j] = 1;
    }
}

void significant_numbers(int b, int e, bool* chk)
{
    int ans = 0;
    
    for (int i = 2; i < bufor; i++)
    {
        if (i * i > e)
        {
            break;
        }
        
        if (!chk[i])
        {
            if (i * i >= b)
                ans++;
        }

    }

    cout << ans << endl;
}

 

---

Jest za wolno bo za każdym razem przeglądasz całą tablicę chk[]. Zauważ, że większość elementów w tej tablicy ma wartość 1, a nas obchodzą tylko te, które mają wartość 0. Możemy więc bezpośrednio trzymać na wektorze takie i, że chk[i] jest równe 0.

---

Wszystko działa. Dziękuje za pomoc i pozdrawiam.