Faktoryzacja [FACTORIZ]

w prosty sposób można przyspieszyć (drobna zmiana w jednej linii) - ale nie jest wystarczające dla wszystkich testów - zresztą wtedy wychodzi błąd algorytmu i jest WA (też łatwe do poprawy)

być może wystarczy sprawdzać podzielność nie przez wszystkie nieparzyste, a tylko te właściwe - ale tego nie sprawdzałem

myślę, że optymalnym rozwiązaniem jest takie, w którym dla danej liczby od razu znamy jej najmniejszy podzielnik - pomyśl o takim rozwiązaniu - rozwiązanie bezsensowne, gdy mamy podać rozkład dla jednej liczby, ale gdy jest ich milion to statystyka robi swoje

Również mam problem z tym zadaniem, próbowałem z różnymi algorytmami, oto link do moim zdaniem najlepszego kodu, w którym użyłem sita Eratsotenesa, próbowałem też bez listy, którą widać w moim kodzie. Oto mój kod (tu był kod)

W takim wypadku dlaczego u mnie nie działa, mimo, że mam "taką tablicę z wszystkimi liczbami pierwszymi do 8000000"?

bo masz błędny (trochę, ale sędzia jest dokładny) algorytm - widać to na zamieszczonym przez ciebie na ideone przykładzie

Tak szczerze siedzę nad tym już trzydziestą którąś godzinę i nadal nie mogę znaleźć tego błędu, ale wydaje mi się, że tablica bool już mniejsza być nie może, próbowałem też zmienić tą listę na tablicę, ale nadal wyskakiwał mi limit czasu.

Ja u siebie poprawiłem linijkę 63 z continue na break ale dalej mam limit czasu.

za mało poprawiłeś - po drobnych poprawkach zadanie zostało zaliczone

użycie tablicy zamiast listy jeszcze nieco by przyspieszyło - czyli taka metoda jest wystarczająca do rozwiązania zadania

sprawdziłem swoje stare rozwiązanie - z kłopotami, gdyż dawało SIGSEGV, po sprawdzeniu wyszło, że brakowało inicjacji 2 zmiennych, i teraz nie wiem, czy wtedy zaliczyło bo był inny kompilator, czy też te kilka znaków znikło w czasie przeprowadzek (obie hipotezy są tak samo mało prawdopodobne)

w każdym razie czas jest nieznacznie lepszy 3,36/4,66 - ale w tym zadaniu głównym kosztem są operacje wejścia/wyjścia - musiałbym użyć fast i/o aby mieć bardziej wiarygodne dane, na ile moja metoda jest szybsza

Zamieniłem liste na tablice i funkcje na te fast io, dalej limit czasu

to jeszcze trochę pomyśl - bo naprawdę tylko kilka linijek zmieniłem w twoim programie aby zaliczyło

w szczególności pomyśl nad kolejnością wykonywanych działań

Trochę nad tym popracowałem i jest AC przy nawet nie najgorszym czasie 1.56s ;D Dzięki wszystkim za pomoc, a kodd usuwam.

Cześć, zrobiłem już kilka wersji rozwiązania i ciągle dostaję TLE. W trakcie testów widzę, że pojawia się liczba 7 - czyli jest blisko. Ale już brak mi pomysłów jak to przyspieszyć.
Ktoś coś podpowie?
Mój kod:

Zrób jeszcze co najmniej dwie wersje:

1. wersja:

main () {
}

A potem drugą:
2. wersja:

main () {
   int a_kuku;
   while (std::cin  >> a_kuku) ; /// nic nie rob
   /// wczytaj jeszcze kilka razy nic
   std::cin  >> a_kuku;
   std::cin  >> a_kuku;
}

Możliwe, że w pierwszej wersji nie zobaczysz 7, ale gdy wyślesz drugą, napewno pojawi się 7, czyli jest blisko.

Moim zdaniem, dwie tablice to stanowczo za dużo, dzisiaj zrobiłem dla testu, wersję zupełnie bez tablic i bez sita. Czas nie jest powalający, ponad 5 sek, ale z tablicowaniem mam o wiele lepszy więc czemu Ty masz problemy?

Pomyś o tym i przeanalizuj jak bardzo nieefektywnie twój program sprawdza np liczbę 2833.
Przy okazji większych liczb, twój program jest błędny, więc testuj naprawdę swój kod albo u siebie albo na ideone dla większego spektrum liczb a nie tylko dla przykładu z zadania, a nie wysyłaj do sprawdzenia na spoja i nie nazywaj tego [sprawdzania] testowaniem, bo to nie jest testowanie. Zrób też test wydajnościowy, a dopiero potem, gdy uzyskasz AC zacznij myśleć jak przyśpieszyć swój kod.

To jest zadanie z kategorii trudnych, więc może powinieneś zacząć od perfekcyjnego rozwiązania łatwiejszych?

Gdy zadanie PRIME_T rozwiążesz w czasie 0.00, to z tym też będzie Ci łatwiej.

Prezent na dzień dziecka, nie tylko dla dzieci

Jeżeli masz kłopot, z wypisaniem gwiazdek w odpowiedniej ilości i w odpowiednich miejscach to jest prezent dla Ciebie:

factor (liczba) {     
   dzielnik = 2;
   dopóki  dzielnik * dzielnik jest mniejszy lub równy liczba 
             jezeli liczba dzieli sie bez reszty przez dzielnik : 
                         wypisz dzielnik  oraz gwiazdkę
                         liczba = liczba podzielona przez dzielnik
             w przeciwnym wypadku powieksz dzielnik 
   /// liczba - po ewentualnym wczesniejszym podzieleniu przez  dzielniki jest liczba pierwsza - i wypisujemy ja bez gwiazdek:
   wypisz liczba
koniec

Powyższy algorytm, można zapisać w dowolnym języku, ale nie gwarantuje on automatycznie AC, np jeżeli będziemy powiększać dzielnik tylko o 1, będzie za wolny. Gwarantuje za to poprawny format wypisywanych danych.

PS
Powyższy prosty algorytm działa także dla liczby jeden, mimo, że jedynka nie jest liczbą pierwszą.

Cześć,
jako że dostaję bez przerwy TLE, podepnę się pod post. Jakieś sugestie, co mogę robić nie tak?
Jeszcze jedno - jak spradzacie szybkość swoich programów?

Można nawet użyć do tego ideone - do sprawdzania szybkości działania, ale napewno wklejając tam “odrobinę” większe testy niż takie jakie tam wkleiłeś. Możliwe, że testujesz u siebie dokładniej, ale jak chcesz pomocy, to postaraj się lepiej, przecież to nawet nie są tak małe testy jak z zadania, to żart a nie test.

Nie wystarczy się podpiąć, należy przeczytać [przestudiować] dokładnie wątek i skorzystać z rad. Na przykład PRIME_T == 0.0 jest wielce pomocne, ale nie wystarczające. Po co robisz sito jak i tak z niego potem nie korzystasz? Nie jestem pewny i nie chcę tego wiedzieć, czy robisz je w ogóle poprawnie.