Zliczanie liczb bezkwadratowych

Prelegent(ci)

Jakub Pawlewicz

Afiliacja

Uniwersytet Warszawski

Termin

14 października 2010 12:15

Pokój

p. 5870

Seminarium

Seminarium "Algorytmika"

---

Liczba bezkwadratowa, to taka, która nie ma dzielników kwadratowych
Liczenie liczby liczb bezkwadratowych nie większych od n dotychczas
potrafiliśmy robić w czasie O(n^1/2). Przedstawię algorytm działający
w czasie O(n^2/5) w pamięci O(n^1/5), który dodatkowo dobrze się
zrównolegla.

Dotychczas największa policzona wartość jest dla n=10^17 (Sloane
A071172). Z użyciem mojej implementacji byłem w stanie policzyć wartość
dla n=10^32 w 2 dni na 6 procesorach.

---