Liczby pierwsze - Zadanie SPOJ -

Question

Witam,

Czy widzicie w tym algorytmie błąd? Moim zdaniem cały program działa, ale nie przechodzi na SPOJ.

Wklejam fragment kodu:

                if(czy_zero==false)
                {
                    for(int j=3; j<=floor(sqrt(tab[i])); j++)
                    {
                        if(tab[i]%j!=0)
                        {
                            czy_zero = false;
                        }
                        else
                        {
                            czy_zero = true;
                            break;
                        }
                    }
                }
                if (czy_zero==false) cout<<"TAK"<<endl;
                else cout<<"NIE"<<endl;

Proszę o ewentualne uwagi do kodu, lub samej logiki. W razie potrzeby wytłumaczę resztę kodu, żeby nie wklejać całego zadania.

Pozdrawiam!

Answer 1

Jaki masz błąd w sprawdzarce? Nie widać w tym kawałku kodu, który wysłałeś błędu, polecam zamiast pisania j<=floor(sqrt(tab[i])), spróbować j * j <= tab[i], oraz j powinno zaczynać od 2, przecież liczba parzysta nie jest pierwsza (chyba, że sprawdzasz podzielność przez 2 gdzie indziej).

Jednak największy problem twojego rozwiązania (wcale nie słabego), będzie jego czas działania. Mamy 100 000 liczb, każdą obsługujemy w pierwiastek z n, gdzie n maksymalnie 10 000, więc pierwiastek z niego to 100. Mamy 100 000 razy 100 operacji, czyli 10^8, co dla spoja będzie za wolne. Złożonośc O( n * pierwiastek z n ).

Zadanie można wykonać w O( n ). Cały trick polega na wykorzystaniu sita erastotenesa, które po 10 000 * log2( 10 000 ) da nam tablice z informacja dla kazdej liczby od 1 do 10 000 czy jest pierwsza. Potem bedziemy wczytywać liczby i sprawdzać "pierwszość" w tablicy. Samo sito to pare linijek kodu, odsyłam na wiki wikipedia

Jeśli nie rozumiesz, co oznacza O(n), to nie ma problemu, o złożoności czasowej możesz poczytać tu: złożoność obliczeniowa

Comments

Hmm.

Racja, jedno to napisać dobre rozwiązanie, a drugie, żeby było ono wydajne!

Ok. Piszę więc drugie podejście do tego.

Dzięki za pomoc.

Answer 2

Rozumiem, ze uwzgledniles wczesniej 1 i 2?

Co do kodu to mozesz aby usprawnic zwiekszac j  o 2 a nie o 1.

Comments

Tak uwzględniłem 1 jako NIE i 2 jako TAK.

Zmieniłem również, żeby pętla rozpoczynała się od 2 zamiast od 3 i nadal nie przechodzi przez SPOJ.

 

               if(czy_zero==false)
                {
                    for(int j=2; j<=floor(sqrt(tab[i])); j++)
                    {
                        if(tab[i]%j!=0)
                        {
                            cout<<"Reszta z dzielenia to: "<<tab[i]%j<<endl;
                            czy_zero = false;
                        }
                        else
                        {
                            czy_zero = true;
                            break;
                        }
                    }
                }

                if (czy_zero==false) cout<<"TAK"<<endl;
                else cout<<"NIE"<<endl;

 

---

Nie widze bledu w algorytmie, pokaz caly kod

---

Oto kod. Usunę po rozwiązaniu:

KOD USUNIETO - watek SEMIROZWIAZANY

---

Dajesz do sprawdzenia spoj'owi fragment z reszta?

---

Niee, to było już w fazie debugowania.

Bez komentarza nie przyjął.

---

Wrzuc sobie ten kod na ideone wpisz liczby od 1 do 10. To Ci da troche do zastanowienia(bool)

Co do kodu nie podoba mi sie to tab[i] oraz ta petla testow moim zdaniem lepiej by dzialalo cos takiego

...
 for(int i=0; i<t; i++)     =>       while(t--)
...
tab[i]==....=> liczba==...