RLNC - Rozkład liczby na czynniki pierwsze - optymalizacja

[kwiatek023]

Cześć. Wykonując to zadanie http://pl.spoj.com/WSDOCPP/problems/RLNC/ wykorzystałem tablicę, w której dla każdej liczby zapisałem jej najmniejszy pierwszy dzielnik (stworzona za pomocą sita Eratostenesa). Następnie dla podanej liczby odczytywałem dzielnik, po czym daną liczbę dzieliłem przez ów dzielnik i tak aż do całego rozkładu. Czy ma ktoś pomysł na przyspieszenie algorytmu? Albo być może powinienem zmienić koncepcje?

[tarpauwatratar]

Szybciej możesz np. najpierw wyznaczyć wszystkie liczby pierwsze w przedziale do sqrt(największa możliwa liczba), a dalej dzielić daną liczbę n przez kolejne liczby pierwsze.

[mariusz193]

też wydaje mi się, że przygotowanie takiej tablicy jest niepotrzebne dla tego zadania (choć może być przydatne dla podobnego) - liczba rozkładanych liczb jest niewielka w stosunku do przedziału (1:1000)
więc bardzo dużo pracy się marnuje
warto by zrobić testy dla ilu liczb, które podejście się opłaca

[kwiatek023]

Z waszą poradą uzyskałem czas 0,16. Dzięki Jednak nadal można to zrobić szybciej, więc jeżeli macie jeszcze jakieś pomysły to byłbym wdzięczny.

[narbej]

Uwagi ogólne. Ułatwiła by mi świadomość [informacja] komu pomagam. Z tego linku: http://pl.spoj.com/WSDOCPP/users/kwiatek023/ wynikałoby, że to twoje pierwsze zadanie, a na foruym pierwsza aktywność, twoje pierwsze pytanie. Dopiero ten link: http://pl.spoj.com/users/kwiatek023/ “rzuca” trochę więcej światła, chociaż zastanawia mnie, co to za instytucja NULL? no i sądziłem, że Poznań jest trochę większy ;-). Moim zdaniem, to pytający powinien trochę rozjaśniać a nie zmuszać pomagających do dodatkowego wysiłku, czyż nie?

Optymalizacja jest drugim [lub którymś następnym] stopniem wtajemniczenia i tak w ciemno trudno tu spekulować. Tablica z sitem jest czasami dobra i pozwala uniknąć czasochłonneg dzielenia, ale czy tak jest tutaj i w twoim wykonaniu? Może można je zrobić lepiej? Tablicę można odsiać też innym, szybszym sitem Atkina. Aby lepiej ocenić zadanie, zrobiłem je, bez użycia sita. Wąskim gardłem często jest i/o i jego przyśpieszenie też może wystarczyć. W tym zadaniu “najlepszy” wynik to 26.27: http://pl.spoj.com/WSDOCPP/ranks/RLNC/start=800, więc twój wynik nie jest taki zły. CO można poprawić lub zoptymalizować w twoim kodzie, bez zaglądnięcia do niego jest trudne.

[kwiatek023]

(tu kiedyś był link) proszę Faktycznie jest to moja pierwsza aktywność na forum, a większy Poznań wziąłem sobie do serca Wcześniej nie chciałem wrzucać kodu, który dawał AC.

[narbej]

1. Trochę szybsze wczytywanie. Dodaj:
   ios::sync_with_stdio(false);
   zamiast endl, zastosuj:
   cout << ‘\n’;
2. Zrezygnuj z sita Poniżej fragment kodu, brakuje np: inicjalizacji wartości i, końca linii i innych drobiazgów

while (i*i <= n)
  if (n % i == 0){
    cout << i << ' ';
    n /= i;
  }
  else
    ++i; 
if (n) cout << n;

3. Jeszcze szybsze wczytywanie - printf / scanf
4. Fast i/o [funkcje z przedrostkiem unlocked_…()]
5. Do powyższego fragmentu, można dodać fragment dla liczb [n] parzystych:

while (n & 1 == 0){
  cout << "2 ";
  n >>= 1;
}

a wcześniej podany [pkt 2] blok zacząć z “trochę” większą wartośćią i , a zakończyć if (n > 1). Dodatkowo wcześniej trzeba dodać warunek dla n == 1. W sumie za dużo zmian, a raczej za mało zysku. Dokładniej zero zysku, w końcu wąskim gardłem jest i/o.

6. “Zabawy” z innymi wersjami kompilatora [opcje kompilacji ustawione są na stałe i nie są dostępne dla użytkowników SPOJ’a]

[kwiatek023]

Dzięki za pomoc. Życzę szczęśliwego Nowego Roku