SeaMonster131 Temat założony przez niniejszego użytkownika |
[C++] Liczby pierwsze » 2012-01-13 19:10:29 Witam ;) Zacząłem sobie robić zadania z "Polskiego SPOJ'a", tak, żeby poćwiczyć. Napisałem 1. program, ale wyrzuca mi przekroczenie limitu czasu, dlatego, jeżeli ktoś robił/robi lub po prostu wie, jak powinny wyglądać tamtejsze zadania to może powie co mam źle? :) #include <cstdio>
int main()
{
int il_testow, liczby[ 100000 ];
bool pierwsze[ 100000 ];
scanf( "%d", & il_testow );
for( int i = 0; i < il_testow; i++ )
{
scanf( "%d", & liczby[ i ] );
pierwsze[ i ] = true;
}
for( int i = 0; i < il_testow; i++ )
{
for( int x = 2; x < liczby[ i ]; x++ )
{
if( liczby[ i ] % x == 0 )
pierwsze[ i ] = false;
}
if( pierwsze[ i ] && liczby[ i ] >= 2 )
printf( "\nTAK" );
else
printf( "\nNIE" );
}
return 0;
}
Podejrzewam, że może chodzić o wczytywanie tych liczb itd, ale jak to można wtedy inaczej zrobić? Input
n - liczba testów n<100000, w kolejnych liniach n liczb z przedziału [1..10000] |
Dziękuję za każdą pomoc :) |
|
Drraven |
» 2012-01-13 19:35:37 Może kwestia optymalizacji? #include <cstdio>
int main()
{
int il_testow, liczby[ 100000 ];
bool pierwsze[ 100000 ];
scanf( "%d", & il_testow );
for( int i = 0; i < il_testow; i++ )
{
scanf( "%d", & liczby[ i ] );
pierwsze[ i ] = true;
for( int x = 2; x < liczby[ i ]; x++ )
{
if( liczby[ i ] % x == 0 )
pierwsze[ i ] = false;
}
if( pierwsze[ i ] && liczby[ i ] >= 2 )
printf( "\nTAK" );
else
printf( "\nNIE" );
}
}
return 0;
} Co prawda jeden for mniej, ale może jednak ?:D |
|
matoł115 |
» 2012-01-13 19:39:03 Proponuję nie lecieć z petlą do liczby tylko do pierwiastka z niej :) Możesz też spróbować Sito Eratostenesa.
Pozdrawiam |
|
SeaMonster131 Temat założony przez niniejszego użytkownika |
» 2012-01-13 19:41:36 Ale po wpisaniu liczby od razu wypisuje się TAK / NIE. A według zadania - moim zdaniem - najpierw powinno podać się ilość testów a następnie liczby, potem każda liczba powinna zostać spr i program powinien dopiero wtedy wypisać TAK / NIE.
Na ideone.com czas wyniósł 0.01s (z danymi wejściowymi dla 3 liczb - 0.02s), więc to chyba wina tego, iż nie powinienem stosować scanf/cin itd, tylko wtedy w jaki sposób to zrobić? :) Na "sztywno" to troche bez sensu? |
|
matoł115 |
» 2012-01-13 19:46:36 Nie wiem jak jest na SPOJU, ale na wroc.pl zawsze piszę programy wczytujące przykład z testu i od razu wypisujący rozwiązanie.
Testy są wtedy akceptowane. Myślę, ze na SPOJU będzie podobnie bo brałem udział w High School Programing League i takie rozwiązania przechodziły.
:) |
|
SeaMonster131 Temat założony przez niniejszego użytkownika |
» 2012-01-13 20:00:46 Hm.. no to zrobiłem tak: #include <cstdio>
int main()
{
int ilTestow = 3;
int liczby[ 3 ] = { 11, 1, 4 };
bool pierwsze[ 3 ];
for( int i = 0; i < ilTestow; i++ )
pierwsze[ i ] = true;
for( int i = 0; i < ilTestow; i++ )
{
for( int x = 2; x < liczby[ i ]; x++ )
{
if( liczby[ i ] % x == 0 )
pierwsze[ i ] = false;
}
if( pierwsze[ i ] && liczby[ i ] >= 2 )
printf( "\nTAK" );
else
printf( "\nNIE" );
}
return 0;
}
Teraz czas wynosi 0.00 - 0.01, lecz jest "błędna odpowiedź" :P |
|
szyx_yankez |
» 2012-01-13 20:10:38 | Na ideone.com czas wyniósł 0.01s (z danymi wejściowymi dla 3 liczb - 0.02s) |
Taa, tyle, że na spoj'u nie ma 2 danych testowych, często dziesiątki/setki.
Był niedawno taki sam temat, poszukaj... |
|
ison |
» 2012-01-13 20:12:07 @SeaMonster131 co Ty żeś teraz najlepszego zrobił? ;D
dane masz wczytać z wejścia, najpierw ilość testów potem liczby, odpowiedzi możesz wypisywać 'na krzyż', wejście i wyjście traktowane są osobno, możesz wypisać odpowiedź dla 1 testu tuż po jego wpisaniu,
w Twoim pierwszym kodzie problem leży w tym, że program jest za wolny ;) ok, testowałeś dla 3 liczb, a spróbuj przetestować dla 100000 liczb. Twoim zadaniem jest znalezienie bardziej optymalnej metody na sprawdzanie czy dana liczba jest pierwsza. |
|
| « 1 » 2 |