spoj i liczby pierwsze

Wlasnie po to dalem ten warunek z pierwiastkami zeby liczba ktora jest wielokrotnascia liczby pierwszej nie byla zaliczna do liczby pierwszej.

właśnie Ci udowodniłem liczbą 77, że pierwiastek nie starczy

Ison dalem jeszcze 7 do wyjatkow i juz bedzie chyba dobrze zawsze mozesz podac mi jeszcze jeden przyklad; D?

oto algorytm na generowanie kontr przykładów do Twojego niedziałającego algorytmu:
weź 2 kolejne liczby pierwsze i pomnóż je przez siebie, ta liczba uwala Twój algorytm (oczywiście to nie jedyne liczby, które nie działają)

7 * 11 = 77
11 * 13 = 143
13 * 17 = 221
i tak dalej

faktycznie ;p

dobrze ze jestes ;)


Edit: Ison czyli tak czy siak trzeba wziąć jakąś liczbę wyjątków prawda ? I ta liczba będzie zależna od tego ile liczb sprawdzamy?

diego997, zaklep sito, i wypisz ~30 pierwszych elementów, to zauważysz, że nie trzeba się bawić w wyjątki ;)

Edit: Ison czyli tak czy siak trzeba wziąć jakąś liczbę wyjątków prawda ? I ta liczba będzie zależna od tego ile liczb sprawdzamy?

Nazywanie tego wyjątkami jest bez sensu, dlaczego akurat mówisz, że 2, 3, 5 to nie są wyjątki a 7, 11, 13 już tak, jak będziesz sprawdzać jakąś dużą liczbę to tych wyjątków będzie mnóstwo. Poczytaj o sicie eratostenesa.

A jakby tylko sprawdzać, czy liczba jest podzielna przez 2..10 ? Jeżeli nie, to jest to liczba pierwsza. Dobrze myślę?

@down:
fakt ;P

nie, liczba może być podzielna tylko przez liczby większe od 10 a nadal być liczbą złożoną,
sprawdź liczby, które podałem wyżej

Akurat się tak składa, że to zadanie robiłem wczoraj na lidze w szkole ;)
W miarę szybki sposób - wygeneruj sobie tablicę liczb pierwszych i wrzuć ją do pliku źródłowego. Potem tylko porównuj input z kolejnymi liczbami z tablicy. Chcesz szybciej?
Jeżeli liczba jest złożona to musi mieć dzielniki albo oba równe sqrt(liczba), albo jeden większy, a drugi mniejszy. , więc wygenerowaną wcześniej tablicę ograniczasz do liczby max 100 (czyli w naszym przypadku 97). Potem input sprawdzasz czy się dzieli przez cokolwiek z tablicy (za pomocą modulo). Dzięki temu mój algo przyspieszył o ok. 4-5 razy ;)

to jest treść zadania: http://pl.spoj.pl/problems/PRIME_T/

zabawmy się trochę w matematykę
n = 10000 zakres danych
czas wykonania Sita Eratostenesa O(n log log n) // log - chodzi i logarytm o podstawie 2.
mamy m (100000) zapytań.
za pomocą tablicy z sita jesteśmy w czasie stałym odpowiadać czy liczba jest pierwsza.
Ogólna złożoność algorytmu to O(n*log(log(n)) + m) można też zapisać O(m).

jesli jednak chcesz sprawdzac liczbę do pierwiastka czy jest pierwsza to złożoność wynosi O(n*(log(log(n)) + m*sqrt(m)),
przyspieszenie typu, ze sprawdzamy czy dzielnikami są 2,3,5 itd., mało wpływa na złożoność (liczb pierwszy jest zadziwiająco dużo).

jakie wnioski z tego można zauważyć
1. jak chcesz sprawdzić czy liczba jest pierwsza, a wiesz że jest < 10^6 to sito styka
2. jak masz liczby >10^6 jednak < 10^12 to trzeba zastosowac 2 metode,
3. jak mamy liczby >10^12 to trzeba kompinować z jakimis heurami ( rozwiazania które czasami dają błędną odpowiedz)