20 / 25
Jun 2020
  1. W programie jest generowana tablica p typu bool z liczbami pierwszymi. Niżej nie jest wykorzystywana.

Wykorzystanie jej NIE gwarantuje wystarczające przyspieszenie. Może być trudno (ale w końcu to trudne zadanie)
Robiłem próby różne i w końcu zrobiłem to zadanie całkiem inaczej.

  1. Na ideone można sprawdzić czas wykonania. Jest niestety ograniczenie na ilość danych wklejonych, więc 1000 000 liczb nie wklei się i nie przetestuje.

Ale do sprawdzenia jak wolne jest moje rozwiązanie nie trzeba wklejać aż tyle, przecież chodzi tylko o porównywanie kolejnych poprawek mojego kodu czy są lepsze czy nie, więc jeżeli dla jakiegoś możliwie dużego testu, na ideone dostaję np 0.05 sek, to muszę tak poprawiać program aby uzyskać krótszy czas dla tego samego testu.

“Surowe” wykorzystanie mojej propozycji gwarantuje TLE, ale zadanie jest trudne. To tylko drobna podpowiedź, jak do zadania można podejść. Można rozwiązać je nawet w BASHU, ale będzie to oczywiście raczej trudne albo może nawet bardzo trudne;-) : https://pl.spoj.com/ranks/FACTORIZ/lang=bash7 i oczywiście nie w taki, powyżej opisany sposób.

Dzięki za pomoc.
Faktycznie - nie zauważyłem, że z sita później nie korzystam.
Wprowadziłem jeszcze kilka poprawek i jest AC.
Jeszcze mam pytanie co do testowania szybkości na ideone - przy większej ilości liczb dostaję komunikat “błąd wykonania”. Czy to oznacza, że osiągnąłem limit danych? Link: https://ideone.com/Xao5Q711

Tak na wyjściu limit danych jest 64kB.
Żeby zobaczyć sukces to w tym przypadku trzeba zamienić w pierwszej linii 9788 na 8754.
(dla liczby większej niż 8754 -> błąd wykonania)