n - maksymalny przedział (0-n)
m - maksymalna liczba przedziałów
Dalej są podawane przedziały.
sito oczywiście znajduje liczby pierwsze
Niestety nie jest to zbyt wydajne, myślę że problemem jest to zliczanie w przedziałach, bo sito jest wydajne.
Przykładowe działanie:
10 5
0 1
1 3
2 7
6 9
8 10
0
2
4
1
0
Kod: http://codepad.org/x8ugiph9
Proszę o jakieś naprowadzenie na wydajniejsze rozwiązanie problemu.
Jeśli działanie sita zwracałoby vector/tablicę liczb pierwszych, a nie maskę mógłbyś wyznaczyć ich ilość wyszukiwaniem binarnym, np. za pomocą:
ilosc = distance(upper_bound(b), lower_bound(a));Tzn musiałbym w funkcji sito przekopiować jedynki do tablicy np. takiej? tab[5] = {2,3,5,7,11}?
Czy to nie spowolniłoby bardzo sita?
Poprawiłem kod.
Będziesz musiał przejść raz po wszystkich liczbach z sita, ale nie będziesz musiał ich liczyć w każdym przedziale, zatem kod powinien być szybszy. Samo sito też dałoby się zoptymalizować.
Jak powinna wyglądać taka tablica?
Trochę nie rozumiem.
Zrobiłem te liczby pierwsze na wektorze:
Czy to jest ok?
#include
#include
#include
#include
using namespace std;
void sito(int dokad, bool *tab, vector &v)
{
tab[0] = 0;
tab[1] = 0;
for(int i = 2; i * i < dokad; ++i)
for(int j = 2; j * i < dokad; ++j)
if(tab[i] == 1) tab[i * j] = 0;
for (int i = 2; i < dokad; ++i)
if (tab[i])
v.push_back(i);
}
int main()
{
const int MAX = 1000000;
bool pierwsze[MAX + 1];
vector vpierwsze;
for (int i = 0; i < MAX; ++i)
pierwsze[i] = 1;
int przedzialy[MAX + 1];
int n, m;
scanf("%d %d", &n, &m);
for(int i = 0; i < 2 * m; ++i)
scanf("%d", &przedzialy[i]);
sito(n + 1, pierwsze, vpierwsze);
int ile_juz = 0;
for(int i = 0; i < 2 * m; i += 2)
{
ile_juz = distance(lower_bound(vpierwsze.begin(), vpierwsze.end(), przedzialy[i]),
upper_bound(vpierwsze.begin(), vpierwsze.end(), przedzialy[i + 1])
);
// for(int j = przedzialy[i]; j <= przedzialy[i + 1]; ++j)
// if(pierwsze[j] == 1)
// ++ile_juz;
printf("%d\n", ile_juz);
}
}
Chodziło mi o coś takiego. Ilość liczb pierwszych we wszystkich przedziałach wyznaczasz w czasie O(n*log(k)), gdzie n to ilość przedziałów, a k ilość wyznaczonych liczb pierwszych zamiast O(n*k).
Dziękuję.
Sprawdziłem w referencjach jak działają *_bound i już wszystko rozumiem. Wielkie dzięki, w ogóle nie znałem tych funkcji.
#include
#include
#include
#include
#include
#include
using namespace std;
typedef vector > arr;
const int ile = 6; /* \ */
const int iloczyn = 2* 3* 5* 7* 11* 13 ; /* > zalezne parametry */
const int pt[] = { 2, 3, 5, 7, 11, 13}; /* / nalezy dobrac do rozmiaru */
/* cache'u w procesorze */
void elim (bool v[], const arr::iterator& start, const arr::iterator& end)
{
int j;
for (arr::iterator it = start; it != end; ++it)
{
if (it->second >= iloczyn)
it->second -= iloczyn;
else
{
for (j = it->second; j < iloczyn; j += it->first)
v[j] = false;
it->second = j - iloczyn;
}
}
}
void sito (bool v[], arr& pierwsze, int d)
{
int j, k;
for (int i = 1; i < iloczyn; ++i)
if (v[i])
{
k = d + i;
for (j = i + k; j < iloczyn; j += k)
v[j] = false;
pierwsze.push_back(make_pair(k, j - iloczyn));
}
}
#define przepisz(skad, dokad) memcpy(dokad, skad, iloczyn)
// void przepisz(bool skad[], bool dokad[]) {
// for (int i = 0; i < iloczyn; ++i)
// dokad[i] = skad[i];
// }
int main()
{
int a = 1, b, sqrtb, t, d = 0, n, l, p;
arr pierwsze, przedzialy;
vector wszystkiep;
bool wzorzec[iloczyn], temp[iloczyn];
for (int i = 0; i < iloczyn; ++i)
wzorzec[i] = true;
cin >> b >> n;
wszystkiep.reserve(1.25506 * b / log(b)); // gorne ograniczenie funkcji pi(n)
for (int i = 0; i < n; ++i)
{
cin >> l;
cin >> p;
przedzialy.push_back(make_pair(l, p));
}
for (int i = 0; i < ile; ++i)
pierwsze.push_back(make_pair(pt[i], 0));
elim(wzorzec, pierwsze.begin(), pierwsze.end());
przepisz(wzorzec, temp);
temp[1] = false;
sito(temp, pierwsze, 0);
sqrtb = (int) sqrt((double) b);
t = sqrtb / iloczyn;
sqrtb = (t + 1) * iloczyn; // zaokraglenie pierwastka do konca przedzialu
for (int i = 0; i < t; ++i)
{
d += iloczyn;
przepisz(wzorzec, temp);
elim(temp, pierwsze.begin() + ile, pierwsze.end());
sito(temp, pierwsze, d);
}
if (a < sqrtb)
{
for (arr::const_iterator it = pierwsze.begin(); it != pierwsze.end(); ++it)
if (it->first <= b && it->first >= a)
wszystkiep.push_back(it->first); // it->first jest pierwsze
}
int ml, ms;
d = sqrtb;
while (b > d)
{
ms = ml = 0;
przepisz(wzorzec, temp);
elim(temp, pierwsze.begin() + ile, pierwsze.end());
if (a > d || b < d + iloczyn)
{
for (int i = 0; i < iloczyn; ++i)
if (temp[i])
wszystkiep.push_back(d + i); //d + i jest pierwsze
}
else
{
for (int i = 0; i < iloczyn; ++i)
if (temp[i])
wszystkiep.push_back(d + i); //d + i jest pierwsze
}
d += iloczyn;
}
for(int i = 0; i < n; ++i)
cout << distance(lower_bound(wszystkiep.begin(), wszystkiep.end(), przedzialy[i].first),
upper_bound(wszystkiep.begin(), wszystkiep.end(), przedzialy[i].second)
)
<< endl;
return 0;
}
Jeśli Cię to jeszcze interesuje, to jest tu działający program z zoptymalizowanym sitem (miałem podobny i przerobiłem). Problemem jest tutaj przechowywanie wszystkich liczb pierwszych w wektorze wszystkiep (szybko braknie pamięci). Można w locie dodawać do przedziałów bez spamiętywania wszystkich liczb pierwszych, ale do tego trzeba jakiejś szybkiej struktury (może jakieś drzewa przedziałowe?).
EDIT:
Poprawka, wziąłem zły logarytm
Hm, fajne (;
Co do szybszej struktury to nie mam pojęcia…