Nie jesteś zalogowany |
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.
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.
