PRIME_T - Liczby Pierwsze

[knucias123]

Siemka byłby ktoś tak miły i powiedział mi co jest nie tak w tym zadaniu,
lub co można ulepszyć żeby działało szybciej

[yula]

http://discuss.spoj.com/search?q=prime_t%20category%3A45 myślę że gdzieś tam znajdziesz odpowiedź… przynajmniej do przyśpieszenia algorytmu na 100%

[zalobowski]

Algorytm nie działa dla większy liczb powinieneś sprawdzić czy liczba jest podzielna przez jakąkolwiek liczbe nie licząc 1 i jej samej (np poprzez napisanie funkcji która zwraca false kiedy liczba nie jest pierwsza).

[yula]

Akurat dla tego zadania ten zakres raczej wystarczy jak dobrze pamiętam, ale za wolno no i parę poprawek trzeba…

[knucias123]

Totalnie uprościłem konstrukcję jest mi ktoś w stanie powiedzieć dlaczego wywala błąd
skoro z teorią sita Erastotenesa to powinno działać

[pawoj20]

1. pierwotny program liczyl prawdopodobnie prawidlowo, ale za wolno. z moich szacunkow w niekorzystnym przypadku liczyl ponad 30 sekund. jaki to moglby byc niekorzystny przypadek? 99 tysiecy liczb do sprawdzenia i kazda z tych liczb jest liczba pierwsza zblizona do 10 000.
2. teraz program liczy na pewno zle. Przyklad - dla liczby 121 podaje ze jest pierwsza.
3. sito Erastotenesa odpowiednio zastosowane przyspieszy wykonanie programu. moglbym podpowiedziec bardziej, ale popsulbym zabawe z rozwiazaniem problemu.

[narbej]

dlaczego wywala błąd, skoro z teorią sita Erastotenesa to powinno działać

Możliwe, że tak [to powinno działać].Tyle tylko, że to nie ma nic ale to nic wspólnego ani z teorią, ani z praktyką ani z algorytmem - sitem Erastotenesa, więc nie bardzo rozumiem, twojego pytania.