Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

[C++] Niepierwsze dzielniki (optymalizacja)

Ostatnio zmodyfikowano 2012-11-13 13:58
Autor Wiadomość
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 ;)

C/C++
// Program zlicza dzielnikki złozone liczby N
#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;
}
P-68926
DejaVu
» 2012-11-10 14:15:26
Frazy, które należy wpisać w wyszukiwarkę google:

http://pl.wikipedia.org/wiki/Sito_Eratostenesa

/edit:
Choć wydaje mi się, że powinieneś nieco lepiej opisać treść zadania, bowiem mam wrażenie, że nie chodzi tu o liczby pierwsze...
P-68927
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ą. 
P-68928
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?

P-68933
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
P-69109
« 1 »
  Strona 1 z 1