You are not logged in |
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.
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.
