Zadanie SPOJ - BFN2

Question

Witam,
czy jest możliwość zoptymalizowania wyświetlania tekstu na ekran w konsoli? Program, który napisałem rozwiązuje zadanie (podaje liczby pierwsze dla zadanego przedziału). Niestety o ile policzenie liczb pierwszych z przedziału <2146000000, 2147000000> zajmuje ok. 0,33s to ich wyświetlenie na ekran niemalże 10s. Używam funkcji setvbuff, a do wyświetlania fprintf.

Answer 1

Problem nie leży w "powolnym printf". Problem leży w wybraniu poprawnego algorytmu: https://pl.wikipedia.org/wiki/Sito_Eratostenesa

Mam nadzieję że wybrałeś właśnie ten. Ew. można jeszcze ten jeśli ktoś chce zaliczyć zadanie: https://pl.wikipedia.org/wiki/Sito_Atkina

Popatrz także na limit pamięci w tym zadaniu. Jest bardzo duży co także sugeruje wybór tego algorytmu :)

Answer 2

Algorytm na sito prezentuję tu: https://www.youtube.com/watch?v=78WNtaMUNFQ

Dotyczy innego zadania, ale w tym zadaniu też trzeba sito zrobić pewnie. 

Comments

Jak byś z tego tłumaczenia usunął użycie VLA, to już było by lepiej :) (15 minuta filmu)

https://godbolt.org/z/PTuPXw

teraz przed int n, dodaj const i zobacz różnicę.

23:42 tę opinię bym sobie darował. Tym bardziej że używanie C::B w OsX już jest "swego rodzaju aberracją" :)

---

1. tak, wiem, że VLA wzbudza pewną niechęć, choć nie wiem czemu aż taką.

To film sprzed 3 lat, teraz stosuję bardziej zapis

 

int n = 1000;

bool * liczby;

liczby = new bool[n];

dlatego, że jest zgodny niemalże w 100% z jawą, a z uczniami przesiadłem się na Javę.

2. Niestety Code::Blocks dla Maka utknął i się nie rozwija i mam problem, bo do matury nie jest dopuszczone żadne środowisko działające pod Makiem. Na szczęście teraz jest Windows 10 i w zasadzie przeniosłem się na Windows 10 z pracą i nagrywaniem filmów, a Code::Blocks pod Windows 10 jest najnowszy i już się tak nie sypie i daje radę.

---

1. tak, wiem, że VLA wzbudza pewną niechęć, choć nie wiem czemu aż taką.

Nie ma VLA w C++. Jest w C99 a w C11 jest już opcjonalny i może po prostu takiej możliwości nie być. Powód jest bardzo prosty. To co wyprawia na stosie assembler by obsłużyć zmienną wielkość tablicy, woła o pomstę. A dlaczego nie ma w C++? Bo do tego teatru dochodzą jeszcze wyjątki i przestaje być śmiesznie.

2. Niestety Code::Blocks dla Maka utknął i się nie rozwija...

Ależ oczywiście że jest. I to jest świeży. Tylko trzeba go instalować na Maku z portów: https://ports.macports.org/port/codeblocks/summary

Tylko zobacz jak jest popularny :) W ciągu ostatnich 30 dni, 2 instalacje (na świecie) :-/ To z tego powodu mówiłem że "to abberracja" :)

 

---

1. OK, OK. Nie będę tego stosował w nowych filmach.

2. O widzisz, dziękuję za wskazówki, spróbuję sobie zasadzić z tych portów.

Ja wiem, że pomysł średni, ale co poradzisz, jak to jest do matury dopuszczone? Zastanawiałem się, żeby na maku robić w Eclipse C++, tak samo jak Javę, ale CKE tego nie przewiduje.