Zliczanie liczb bezkwadratowych

Speaker(s)

Jakub Pawlewicz

Affiliation

Uniwersytet Warszawski

Date

Oct. 14, 2010, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

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.

---