[bart606]

Mam zadanie ze spoj liczb pierwszych, wiem, że jest pełno rozwiązań w necie, ale chciałem jakoś po swojemu.

Wiem, że poziom dla Was zarabiających po 10k/mies śmieszny, no ale uczę się.

Powiedzcie czy ma to jakikolwiek sens i może jakieś porady.

Użytkownik podaje liczbę np. 11. Program ifem i modulo dzieli przez 2, jeśli jest reszta z dzielenia, to pomocnicza zmienna przyjmuje 1 a jak nie, to 0. Później na tej samej zasadzie dzieli przez 3 i jeśli suma obu pomocniczych zmiennych da 2, to jest to liczba pierwsza else - nie jest.

#programowanie #cpp #uczesie

[koob]

@bart606: masz tylko sprawdzic czy liczba jest pierwsza czy nie jest ?

[n.....l]

@bart606: Zamiast dodawać do zmiennych pomocniczych zrób sobie warunek and w if.

np. if ((l1 % 2 != 0) && (l2 % 3 != 0))

[bart606]

@koob: tak, a później wypisać tylko "tak" - jeśli pierwsza i "nie" jeśli nie.

[koob]

@bart606: no to lec od i=2 do sqrt(liczba) i sprawdzaj modulo jak znajdziesz == 0 to nie jest pierwsza

[marooned]

@bart606: A później dzieli przed 4 ? Jeśli tak będziesz robić niepotrzebne obliczenia. Poczytaj o Sicie Eratostenesa.

[koob]

@marooned: oczywiscie da sie to zoptymalizowac to co napisalem to wersja basic

[beret20022]

@bart606: Twój sposób ma sens jak najbardziej, tylko trzeba troche uogólnić to co mowisz. Bo co jeśli np odpalisz swoj program dla jakiegoś większego k, którego nie dzieli ani 2 ani 3, ale dzieli jakaś inna liczba pierwsza?

[bart606]

@nvll: Po swojemu nie mogłem, a Twój działa. Dzięki.

@marooned: Po co przez 4, skoro wystarczy przez 2?

@beret20022: Jakiś przykład tego k?

Narazie mam tak jak na obrazku. Chyba wystarczy, że uzupełnię o ilość powtórzeń podawaną przez użytkownika i będzie ok.

Tak w ogóle, to treść zadania (mamy nie robić na tablicach):

"Sprawdź, które spośród danych liczb są liczbami pierwszymi

Input

n - liczba testów n<100000, w kolejnych

[k.....r]

@bart606: zrob sobie preprocessing do sqrt(sqrt(max))

[Hauleth]

@bart606: Wbij na sztywno ogromnego

switch

a zawierającego wszystkie liczby pierwsze. Najszybsze rozwiązanie (testowane).

[marooned]

@bart606: No dobra, ale teraz sprawdzasz tylko podzielność przez 2 i 3. Żeby przetestować inne dzielniki będziesz musiał zrobić pętlę i najlepiej zapamiętać wielokrotności liczb pierwszych które już sprawdziłeś. Czyli 4 np. I tutaj pojawia się Sito Eratostenesa . Chyba nie chcesz tworzyć tylu ifów aby starczyło do n=10000.? Albo lecieć po wszystkich potencjalnych dzielnikach < sqrt(n).

[Hauleth]

@kuhar:

sqrt(max)

przy sicie Eratostenesa.

[k.....r]

@Hauleth: no, ale preprocessing sobie wystarczy do sqrt(sqrt(max)) zrobic

[beret20022]

@bart606: Chociażby 49

[Hauleth]

@kuhar: Najwydajniejszy będzie wielki

switch

:D (serio, testowałem).

[k.....r]

@Hauleth: daj link do konkretnego zadania i sie przekonamy

[Hauleth]

@kuhar: Tego, o które się tu rozchodzi: http://pl.spoj.com/problems/PRIME_T/.

[k.....r]

@Hauleth: ok, rzucam wyzwanie na njszybsze rozwiazanie, czas do polnocy, pasuje?

[Hauleth]

@kuhar: Ja mam 0.2s. Nie mam już pomysłu jak to jeszcze bardziej usprawnić. Ewentualne sugestie mile widziane.

Wróć. Najlepiej mam 0.12s.

[k.....r]

@Hauleth: podaj nick na spoju