Sito aratostenesa optymalizacja

Sito aratostenesa optymalizacja
TA
  • Rejestracja:około 6 lat
  • Ostatnio:ponad 4 lata
  • Postów:37
0

Witam piszę tutaj po raz któryś. Ucze się jakiś miesiąc języka c++ (Łącznie z przerwami) i mam cały czas problem z optymalizacją kodu do jak najlepszej złożoności.

Zadanie oczywiście ze spoj-a polega na wyznaczeniu liczb pierwszych w zakresie. Problem? Przekroczono limit czasu:/

Ma ktoś wiedzę dzięki czemu mogę to lepiej zoptymalizować? Szukając w internecie znalazłem kilka innych ale prawie wszystkie bazują na tym samym.
Proszę jedynie o informacje która bilbioteka lub co może tutaj pomóc, dalej sam już znajdę nie chcę żebyście rozwiązywali problem za mnie.

Link do zadania: https://www.spoj.com/problems/PRIME1/

Kod mojego brzydala:

Kopiuj
#include <iostream>
#include <math.h>

using namespace std;


void licz(long long int &a, long long int &b)
{
    bool *zbior= new bool[b+1];
    for(int i=2; i<=b; i++)
    {
        zbior[i]=true;
    }
    for(int i=2; i<=sqrt(b); i++)
    {
        if(zbior[i]==true)
        {
            for(int j=i*i; j<=b; j+=i)
            {
                zbior[j]=false;
            }
        }
    }
    for(int i=2; i<=b; i++)
    {
        if((zbior[i]==true)&&(i>=a))
        {
            cout<<i<<endl;
        }
    }
}

int main()
{
    int proby;
    long long int zakres1,zakres2;
    cin>>proby;
    while(proby!=0)
    {
        cin>>zakres1>>zakres2;
        while((1>zakres1>zakres2>1000000000)||(zakres2-zakres1>100000))
        {
            cout<<"Zle wpisane dane, wpisz ponownie liczby musza spelniac warunki 1 <= a <= b <= 1000000000, b-a<=100000, nie rozpoczniesz zadania dopoki tego nie zrobisz."<<endl;
            cin>>zakres1>>zakres2;
        }
        licz(zakres1,zakres2);
        proby--;
    }
    return 0;
}
edytowany 1x, ostatnio: TenAnonim
MarekR22
Moderator C/C++
  • Rejestracja:około 17 lat
  • Ostatnio:minuta
1
  1. Must read: https://dsp.krzaq.cc/post/176/ucze-sie-cxx-kiedy-uzywac-new-i-delete/
  2. gdzie w treści zadania jest napisane, że masz wypisywać: ""Zle wpisane dane, wpisz ponownie liczby musza ..... "?
  3. Sito masz policzyć RAZ, na uruchomienie aplikacji, a ty liczysz go za każdym razem, gdy dostajesz nowy zakres!
  4. To jest jedno z tych głupich zadań, gdzie operacje IO są wąskim gardłem dopisz:
Kopiuj
    std::ios::sync_with_stdio (false);
    std::cin.tie(nullptr);

Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.
edytowany 3x, ostatnio: MarekR22
TA
Znam to, czytałem kiedyś. Myślałem o zrobieniu tego na wektorze ale wtedy przesuwają mi się indeksy liczb, no i problem kolejny jest taki że wektor nieco dłużej wszystko wykonuje. Mimo wszystko zrobienie tablicy liczb pierwszych do 1,000,000,000 zajmie temu kodowi za dużo czasu.
TA
Ok idę zmieniać. Zobaczymy co z tego wyjdzie, dzięki za informacje.
TA
  • Rejestracja:około 6 lat
  • Ostatnio:ponad 4 lata
  • Postów:37
0

Errory przy wykorzystaniu:

Kopiuj
std::ios::sync_with_stdio (false);
std::cin.tie(nullptr);

specializing member 'std::basic_ios<char>::sync_with_stdio' requires 'template<>' syntax| <= Zupełnie nie rozumiem.
'cin' does not name a type; did you mean 'sin'?| <= Że co? Jak nie jest jak jest?

edytowany 1x, ostatnio: TenAnonim
MarekR22
Moderator C/C++
  • Rejestracja:około 17 lat
  • Ostatnio:minuta
1

https://wandbox.org/permlink/MyBmkg2cteieMHLQ
https://wandbox.org/permlink/ZcQDH9cxLLdzAwbS

na dodatek popatrz co krzyczy kompilator:

Kopiuj
prog.cc:43:17: warning: comparisons like 'X<=Y<=Z' do not have their mathematical meaning [-Wparentheses]
   43 |         while((1>zakres1>zakres2>1000000000)||(zakres2-zakres1>100000))
      |                ~^~~~~~~~

Pewnie wpisałeś ten fragment poza funkcją stąd błedy. Może powinieneś wrócić do podstaw i książki z której korzystasz?


Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.
edytowany 2x, ostatnio: MarekR22
TA
Naprawione, jedno pytanie jaka jest maksymalna wielkość wektora <bool>? 1,000,000,000?
enedil
  • Rejestracja:ponad 11 lat
  • Ostatnio:2 dni
  • Postów:1027
2
MarekR22 napisał(a):
  1. Must read: https://dsp.krzaq.cc/post/176/ucze-sie-cxx-kiedy-uzywac-new-i-delete/
  2. gdzie w treści zadania jest napisane, że masz wypisywać: ""Zle wpisane dane, wpisz ponownie liczby musza ..... "?
  3. Sito masz policzyć RAZ, na uruchomienie aplikacji, a ty liczysz go za każdym razem, gdy dostajesz nowy zakres!
  4. To jest jedno z tych głupich zadań, gdzie operacje IO są wąskim gardłem dopisz:
Kopiuj
    std::ios::sync_with_stdio (false);
    std::cin.tie(nullptr);

Zupełnie błędne rady nr 3 i 4 (czyli te istotne).
Liczba przypadków testowych to 10, a wielkość każdego zakresu to maksymalnie 10000, w którym jest maksymalnie jakoś 1500 liczb pierwszych, tak więc na wejściu będzie max 20 liczb, a na wyjściu max 15000, czyli dostatecznie mało, żeby się nie przejmować.
Rada 3: w tym zadaniu akurat robiąc sito wiele razy, osiąga się lepszy czas (tylko trzeba to robić trochę sprytnej niż autor), niż robiąc je tylko raz. Nie przemyślałeś tematu.

Zobacz pozostałe 3 komentarze
enedil
@MarekR22: z tym że nie przejdzie, bo sito działa w czasie n log(n) log(log(n)), a dla miliarda to daje jakieś 150 miliardów operacji, czyli coś co się wykonuje z dwie godziny.
TA
Siedze nad tym od kilku godzin, przerobilem atkinsa i jest wolniejszy od tego co zrobilem na poczatku... Masz jakis pomysl co moge zrobic? Przeniesienie tego na wektor mnie wkurza bo nie wiem jak to zrobic z typem bool...
enedil
No, wróć do naiwnej wersji i pomyśl co, z tego co liczysz, nigdy się nie przyda.
TA
Liczby które nie są pierwszymi... Tylko to może być nieprzydatne.
enedil
Większość liczb pierwszych też się nie przyda.
lion137
  • Rejestracja:około 8 lat
  • Ostatnio:mniej niż minuta
  • Postów:4893
2

Naiwne sito, jak zauważyli piszący w tym wątku, albo będzie za wolne, albo przekroczy limit pamięci. Spróbuj tym:
https://en.wikipedia.org/wiki/Sieve_of_Atkin
Zakresy nie są zbyt duże (100000), można zaryzykować metodę naiwną, z dobrym testem (Miller Rabin). Do miliarda to [Miller Rabin] będzie praktycznie O(1).


edytowany 1x, ostatnio: lion137
enedil
Lol, to jest naprawdę proste zadanie. Kombinujesz niepotrzebnie.
lion137
Nie kombinuję, nie chce mi się sprawdzać, ale uważam, że naiwne sito nie przejdzie; za to naiwne rozwiązanie z Miller Rabin tak.
enedil
Z tym się zgadzam, naiwne sito nie przejdzie, ale sito Atkina w tej kwestii jest tak samo słabe. Potrzeba nieco innego typu modyfikacji. Oczywiście, jest szansa że z Rabinem Millerem przejdzie, natomiast jest to głupkowate rozwiązanie, bo uczy tylko, że musisz coś znać, zanim zrobisz zadanie. A w tym zadaniu wystarczy troszkę pomyśleć.
enedil
  • Rejestracja:ponad 11 lat
  • Ostatnio:2 dni
  • Postów:1027
1

Żeby udowodnić, że się da, i to całkiem szybko, wystarczy rzucić okiem:
Imgur

edytowany 1x, ostatnio: enedil
lion137
Zgaduję, segmented sieve i scanf?
enedil
A co to segmented sieve? scanfa nie używałem, normalnie strumienie, z wyłączoną synchronizacją.
TA
Ummm, kiedyś także tak będę umiał... Pierwsza sprawa to wylaczenie synchonizacji ok to wiem jak zrobic i o co chodzi ale dlaczego wiekszosc liczb pierwszych sie nie przyda? Musze miec wszystkie poniewaz nie wiem jakie beda a zakres jest do 1mld.
enedil
Co? Nie, synchronizacja nie ma żadnego znaczenia w tym zadaniu.
enedil
Większość liczb pierwszych się nie przyda, bo masz wygenerować tylko te z zakresu, a one nie mogą się przez wiele liczb dzielić.
TA
Dobra za głupi na to jestem, kiedyś pewnie do tego wrócę, dziękuję za pomoc wszystkim którzy ją okazali.
Kliknij, aby dodać treść...

Pomoc 1.18.8

Typografia

Edytor obsługuje składnie Markdown, w której pojedynczy akcent *kursywa* oraz _kursywa_ to pochylenie. Z kolei podwójny akcent **pogrubienie** oraz __pogrubienie__ to pogrubienie. Dodanie znaczników ~~strike~~ to przekreślenie.

Możesz dodać formatowanie komendami , , oraz .

Ponieważ dekoracja podkreślenia jest przeznaczona na linki, markdown nie zawiera specjalnej składni dla podkreślenia. Dlatego by dodać podkreślenie, użyj <u>underline</u>.

Komendy formatujące reagują na skróty klawiszowe: Ctrl+B, Ctrl+I, Ctrl+U oraz Ctrl+S.

Linki

By dodać link w edytorze użyj komendy lub użyj składni [title](link). URL umieszczony w linku lub nawet URL umieszczony bezpośrednio w tekście będzie aktywny i klikalny.

Jeżeli chcesz, możesz samodzielnie dodać link: <a href="link">title</a>.

Wewnętrzne odnośniki

Możesz umieścić odnośnik do wewnętrznej podstrony, używając następującej składni: [[Delphi/Kompendium]] lub [[Delphi/Kompendium|kliknij, aby przejść do kompendium]]. Odnośniki mogą prowadzić do Forum 4programmers.net lub np. do Kompendium.

Wspomnienia użytkowników

By wspomnieć użytkownika forum, wpisz w formularzu znak @. Zobaczysz okienko samouzupełniające nazwy użytkowników. Samouzupełnienie dobierze odpowiedni format wspomnienia, zależnie od tego czy w nazwie użytkownika znajduje się spacja.

Znaczniki HTML

Dozwolone jest używanie niektórych znaczników HTML: <a>, <b>, <i>, <kbd>, <del>, <strong>, <dfn>, <pre>, <blockquote>, <hr/>, <sub>, <sup> oraz <img/>.

Skróty klawiszowe

Dodaj kombinację klawiszy komendą notacji klawiszy lub skrótem klawiszowym Alt+K.

Reprezentuj kombinacje klawiszowe używając taga <kbd>. Oddziel od siebie klawisze znakiem plus, np <kbd>Alt+Tab</kbd>.

Indeks górny oraz dolny

Przykład: wpisując H<sub>2</sub>O i m<sup>2</sup> otrzymasz: H2O i m2.

Składnia Tex

By precyzyjnie wyrazić działanie matematyczne, użyj składni Tex.

<tex>arcctg(x) = argtan(\frac{1}{x}) = arcsin(\frac{1}{\sqrt{1+x^2}})</tex>

Kod źródłowy

Krótkie fragmenty kodu

Wszelkie jednolinijkowe instrukcje języka programowania powinny być zawarte pomiędzy obróconymi apostrofami: `kod instrukcji` lub ``console.log(`string`);``.

Kod wielolinijkowy

Dodaj fragment kodu komendą . Fragmenty kodu zajmujące całą lub więcej linijek powinny być umieszczone w wielolinijkowym fragmencie kodu. Znaczniki ``` lub ~~~ umożliwiają kolorowanie różnych języków programowania. Możemy nadać nazwę języka programowania używając auto-uzupełnienia, kod został pokolorowany używając konkretnych ustawień kolorowania składni:

```javascript
document.write('Hello World');
```

Możesz zaznaczyć również już wklejony kod w edytorze, i użyć komendy  by zamienić go w kod. Użyj kombinacji Ctrl+`, by dodać fragment kodu bez oznaczników języka.

Tabelki

Dodaj przykładową tabelkę używając komendy . Przykładowa tabelka składa się z dwóch kolumn, nagłówka i jednego wiersza.

Wygeneruj tabelkę na podstawie szablonu. Oddziel komórki separatorem ; lub |, a następnie zaznacz szablonu.

nazwisko;dziedzina;odkrycie
Pitagoras;mathematics;Pythagorean Theorem
Albert Einstein;physics;General Relativity
Marie Curie, Pierre Curie;chemistry;Radium, Polonium

Użyj komendy by zamienić zaznaczony szablon na tabelkę Markdown.

Lista uporządkowana i nieuporządkowana

Możliwe jest tworzenie listy numerowanych oraz wypunktowanych. Wystarczy, że pierwszym znakiem linii będzie * lub - dla listy nieuporządkowanej oraz 1. dla listy uporządkowanej.

Użyj komendy by dodać listę uporządkowaną.

1. Lista numerowana
2. Lista numerowana

Użyj komendy by dodać listę nieuporządkowaną.

* Lista wypunktowana
* Lista wypunktowana
** Lista wypunktowana (drugi poziom)

Składnia Markdown

Edytor obsługuje składnię Markdown, która składa się ze znaków specjalnych. Dostępne komendy, jak formatowanie , dodanie tabelki lub fragmentu kodu są w pewnym sensie świadome otaczającej jej składni, i postarają się unikać uszkodzenia jej.

Dla przykładu, używając tylko dostępnych komend, nie możemy dodać formatowania pogrubienia do kodu wielolinijkowego, albo dodać listy do tabelki - mogłoby to doprowadzić do uszkodzenia składni.

W pewnych odosobnionych przypadkach brak nowej linii przed elementami markdown również mógłby uszkodzić składnie, dlatego edytor dodaje brakujące nowe linie. Dla przykładu, dodanie formatowania pochylenia zaraz po tabelce, mogłoby zostać błędne zinterpretowane, więc edytor doda oddzielającą nową linię pomiędzy tabelką, a pochyleniem.

Skróty klawiszowe

Skróty formatujące, kiedy w edytorze znajduje się pojedynczy kursor, wstawiają sformatowany tekst przykładowy. Jeśli w edytorze znajduje się zaznaczenie (słowo, linijka, paragraf), wtedy zaznaczenie zostaje sformatowane.

  • Ctrl+B - dodaj pogrubienie lub pogrub zaznaczenie
  • Ctrl+I - dodaj pochylenie lub pochyl zaznaczenie
  • Ctrl+U - dodaj podkreślenie lub podkreśl zaznaczenie
  • Ctrl+S - dodaj przekreślenie lub przekreśl zaznaczenie

Notacja Klawiszy

  • Alt+K - dodaj notację klawiszy

Fragment kodu bez oznacznika

  • Alt+C - dodaj pusty fragment kodu

Skróty operujące na kodzie i linijkach:

  • Alt+L - zaznaczenie całej linii
  • Alt+, Alt+ - przeniesienie linijki w której znajduje się kursor w górę/dół.
  • Tab/⌘+] - dodaj wcięcie (wcięcie w prawo)
  • Shit+Tab/⌘+[ - usunięcie wcięcia (wycięcie w lewo)

Dodawanie postów:

  • Ctrl+Enter - dodaj post
  • ⌘+Enter - dodaj post (MacOS)