Liczby pierwsze - optymalizacja

pytanie zadane 16 lutego 2017 w SPOJ przez marcingrychtol Obywatel (1,490 p.)
edycja 17 lutego 2017 przez marcingrychtol

//usunięto rozwiązanie zadania

Zaliczyłem swoje pierwsze zadanie na SPOJu. Chciałbym jakoś zoptymalizować kod, gdyż widzę, że najszybsze wyniki mają 0.00s, a mi pokazuje 0,15s, rekordowo 0,11s - czyli całkiem sporo do skrócenia. Znalazłem na razie taki tip, żeby pętlę dzielącą wrzucić do odrębnej funkcji - ale czy to faktycznie jest w stanie przyspieszyć program kilkanaście razy?

Zamiast ostatniego ifa, miałem wcześniej switcha, który w zależności od wartości zmiennej "czypierwsza" wyrzucał odpowiedź, ale jego zmiana nic nie dała.

Czy jest jeszcze coś innego, o czym nie wiem?

2 odpowiedzi

odpowiedź 16 lutego 2017 przez manjaro Nałogowiec (37,420 p.)
wybrane 17 lutego 2017 przez marcingrychtol

Najlepsza

Zaimplementuj ten algorytm i zejdziesz do 0.00s.

komentarz 17 lutego 2017 przez marcingrychtol Obywatel (1,490 p.)

Widziałem to wcześniej, ale nie byłem pewien jak to zaimplementować. Rozumiem, że powinienem sobie utworzyć tablicę liczb pierwszych o wartościach w zakresie 0..100 i jedna więcej (bo pierwiastek z 10 000), a potem liczbę podaną do sprawdzenia dzielić kolejno nie przez i++, tylko przez wartości z tablicy, a inkrementować tylko jej indeks?

komentarz 17 lutego 2017 przez manjaro Nałogowiec (37,420 p.)
edycja 17 lutego 2017 przez manjaro

Też tak zrobiłem za pierwszym razem ale jest to trochę mało eleganckie. Lepiej to zrobić bez tworzenia ręcznie takich tablic. Przy zadaniu Dyzio zastosowałem taki kod do tworzenia tablicy miliona liczb pierwszych. Obczaj to i ewentualnie przerób. Jeżeli znajdzie liczbę która nie jest pierwsza to wpisuje do tablicy 1. Tam gdzie zostało 0 mamy liczbę pierwszą.

       unsigned int *pierwsze;
       pierwsze = new unsigned int [1000000];
 
        for (unsigned int i=2; i<=1000; i++){
          if (pierwsze[i]==0) {
              for (unsigned int j=2*i; j<=1000000; j+=i){
                  pierwsze[j]=1;
              }
          }
        }

komentarz 17 lutego 2017 przez marcingrychtol Obywatel (1,490 p.)

Czyli sito ma de facto nie zajmować się działaniami na liczbach, tylko "wykreślaniem" pól z tablicy, a sama tablica nie zawiera liczb pierwszych tylko ich znaczniki?

komentarz 18 lutego 2017 przez manjaro Nałogowiec (37,420 p.)

Dokładnie tak. Później możesz z taką tablicą robić co chcesz. Sumować liczby pierwsze albo zliczać ich ilość. Taka uwaga jeszcze - w tej tablicy trzeba jeszcze zmodyfikować 2 pierwsze liczby czyli pierwsze[0] i pierwsze[1] bo one nie są też pierwsze. Albo po prostu pamiętać że liczymy od pierwsze[2] bo 2 jest początkową liczbą pierwszą.

odpowiedź 16 lutego 2017 przez Żyrosławw Bywalec (2,300 p.)

Najlepiej byłoby wybrać lepszy algorytm, w tym najprawdopodobniej tkwi szkopuł. Rzeczy takie jak wrzucanie pętli while do innej funkcji nie poprawią szybkości działania programu, a jedynie jego czytelność :)