[C++] Niepierwsze dzielniki (optymalizacja)
Ostatnio zmodyfikowano 2012-11-13 13:58
Paulina Temat założony przez niniejszego użytkownika |
[C++] Niepierwsze dzielniki (optymalizacja) » 2012-11-10 14:13:44 Witam wszystkich forumowiczów ;) Mam problem z zadaniem. Mam wczytać liczbę mniejszą od 10^8, a program ma podać mi liczbę jej niepierwszych dzielników. W moim programie wszystko działa lecz jest zbyt wolny i program, do którego wrzucamy rozwiązania pokazuje mi komunikat, że przekroczono limit czasu (gdy sprawdza duże wartości liczbowe.) Jak mogę przeformułować mój program? Dziękuje za pomoc ;) #include <iostream> using namespace std;
int main() { int N, z, c; int licznik = 0; cin >> N; if( 1 <= N <= 100000000 ) { for( int i = 2; i <= N; i++ ) { if( N % i == 0 ) { z = i; for( c = 2; c < z; c++ ) { if( z % c == 0 ) { licznik = licznik + 1; break; } } } } } cout << licznik << endl; return 0; }
|
|
DejaVu |
» 2012-11-10 14:15:26 |
|
Paulina Temat założony przez niniejszego użytkownika |
» 2012-11-10 14:38:57 Sito Eratostenesa raczej nie wchodzi w grę, ponieważ zuzywa jeszcze więcej pamieci i czasu (tak już próbowałam też) W zadaniu chodzi o to, że podaję liczbę np. 10 a program daje mi wynik 1, ponieważ wszystkie dzielniki dziesiściu to : 1, 2, 5, 10. A tylko jeden z pośród nich, czyli 10, jest liczbą złożoną. |
|
DejaVu |
» 2012-11-10 16:04:29 Twój problem generalnie sprowadza się do szybkiego znalezienia dzielników liczby http://www.math.edu.pl/podzielnosc-liczb. Problem w tym, że wszystkie dzielniki złożone można rozbić do postaci dzielników prostych, a więc ten sam problem można rozwiązać na wiele sposobów. Być może w tym zadaniu chodzi o znalezienie NWD, a zatem może algorytm Euklidesa warto zaimplementować? http://www.math.edu.pl/algorytm-euklidesa. A może wystarczy napisać po prostu printf( "1\n" ); w przypadku znalezienia co najmniej jednego dzielnika złożonego? |
|
akwes |
» 2012-11-13 13:58:13 Sito Eratostenesa raczej nie wchodzi w grę, ponieważ zuzywa jeszcze więcej pamieci i czasu
|
To co za problem zrobić program, który spisze wynik swoich obliczeń z sita do pliku *.txt w postaci int tab[] = { 2, 3, 5, 7, 11, 13, 17 } // (na przykład)
Potem to co znajdziemy w tym pliku tekstowym kopiujemy do kodu C++ i mamy gotową tablicę bez obliczeń. Przydatne na zadania ze SPOJa |
|
« 1 » |