mati1995g Temat założony przez niniejszego użytkownika |
Wyznaczanie ilości dzielników » 2014-10-28 17:51:23 Witam napisałem program do konkursu na wyznaczanie ilości dzielników lecz działa on zbyt wolno, dokładanie o 0,3s. Może jest ktoś w stanie jakoś pomóc ? ( Liczby są z zakresu od 1 do 10.000.000 i może być ich wprowadzonych maksymalnie 60.002, ostatnia liczba to 0.). Z tego co wiem podobno pomoże przepisanie na C lecz jednak wolałbym zostać przy c++. #include <iostream>
using namespace std;
const int n = 10000000;
bool tablica[ n + 1 ];
int main()
{
ios_base::sync_with_stdio( 0 );
for( int i = 2; i * i <= n; i++ )
{
if( tablica[ i ] == true )
continue;
for( int j = 2 * i; j <= n; j += i )
tablica[ j ] = true;
}
int x;
int lp;
int w;
int nt;
int tab[ 60002 ];
for( int x = 0; x < 60002; x++ ) {
cin >> tab[ x ];
if( tab[ x ] == 0 ) break;
}
x = 0;
while( tab[ x ] > 0 ) {
lp = 1;
nt = 1;
while( tab[ x ] > 1 ) {
nt = nt + 1;
w = 0;
while( tablica[ nt ] == true ) nt = nt + 1;
while( tab[ x ] % nt == 0 ) {
w = w + 1;
tab[ x ] = tab[ x ] / nt;
}
lp = lp *( w + 1 );
}
x++;
cout << lp << endl;
}
return 0;
}
|
|
Tomek_z_W11 |
» 2014-10-30 12:18:31 Na moje oko to przekombinowales...
Spojrz na to, okomentowalem, zeby jasniej bylo:
#include<iostream>
using namespace std;
int main()
{
int ile_liczb; //zmienna przechowujaca rozmiar tablicy - ilosc wprowadzonych liczb
cin >> ile_liczb; //pobranie ilosci liczb, tzn dla ilu liczb program ma obliczyc ilosc dzielnikow
int i, j, licznik=0; //do petli, do zliczania dzielnikow
int tablica_liczb[ile_liczb];
for(i=0; i<ile_liczb; i++)
{
cin >> tablica_liczb; //pobranie wszystkich liczb
}
cout << endl;
for(i=0; i<ile_liczb; i++) //petla idaca po wszystkich komorkach tablicy (od zera ro rozmiaru tablicy)
{
for(j=1; j<=tablica_liczb/2; j++) //petla potrzebna do wylapania wszystkich dzielnikow, idziemy od 1, bo przez 0 nie mozna
{ //dzielic, do tab_liczb/2, bo nie ma potrzeby isc do konca liczby, tzn:
if(tablica_liczb%j==0) //majac liczbe 18, nie znajdziemy dzielnika wiekszego od 9, oprocz 18, ten przypadek
{ //zostal uwzgledniony.
licznik++; //zliczanie dzielnikow
}
}
licznik++; //uwzglednienie przypadku, ze kazda liczba jest podzielna przez sama siebie
cout << licznik << endl;
licznik=0;
}
return 0;
}
Z racji znacznie mniejszej ilosci petli, moj program raczej na pewno sie szybciej wykona. |
|
mati1995g Temat założony przez niniejszego użytkownika |
» 2014-10-30 12:31:29 Błąd kompilacji
/tmp/judge/POD_{87634489-7147-4a0b-bf89-13d0f24b9c9f}/solution.cpp: In function ‘int main()’:
/tmp/judge/POD_{87634489-7147-4a0b-bf89-13d0f24b9c9f}/solution.cpp:15: error: no match for ‘operator>>’ in ‘std::cin >> tablica_liczb’
/usr/lib/gcc/i386-redhat-linux6E/4.4.7/../../../../include/c++/4.4.7/istream:119: note: candidates are: std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(std::basic_istream<_CharT, _Traits>& (*)(std::basic_istream<_CharT, _Traits>&)) [with _CharT = char, _Traits = std::char_traits]
/usr/lib/gcc/i386-redhat-linux6E/4.4.7/../../../../include/c++/4.4.7/istream:123: note: std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(std::basic_ios<_CharT, _Traits>& (*)(std::basic_ios<_CharT, _Traits>&)) [with _CharT = char, _Traits = std::char_traits]
/usr/lib/gcc/i386-redhat-linux6E/4.4.7/../../../../include/c++/4.4.7/istream:130: note: std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(std::ios_base& (*)(std::ios_base&)) [with _CharT = char, _Traits = std::char_traits]
/usr/lib/gcc/i386-redhat-linux6E/4.4.7/../../../../include/c++/4.4.7/istream:166: note: std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(bool&) [with _CharT = char, _Traits = std::char_traits]
/usr/lib/gcc/i386-redhat-linux6E/4.4.7/../../../../include/c++/4.4.7/istream:170: note: std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(short int&) [with _CharT = char, _Traits = std::char_traits]
/usr/lib/gcc/i386-redhat-linux6E/4.4.7/../../../../include/c++/4.4.7/istream:173: note: std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(short unsigned int&) [with _CharT = char, _Traits = std::char_traits]
/usr/lib/gcc/i386-redhat-linux6E/4.4.7/../../../../include/c++/4.4.7/istream:177: note: std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(int&) [with _CharT = char, _Traits = std::char_traits]
/usr/lib/gcc/i386-redhat-linux6E/4.4.7/../../../../include/c++/4.4.7/istream:180: note: std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(unsigned int&) [with _CharT = char, _Traits = std::char_traits]
/usr/lib/gcc/i386-redhat-linux6E/4.4.7/../../../../include/c++/4.4.7/istream:184: note: std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(long int&) [with _CharT = char, _Traits = std::char_traits]
/usr/lib/gcc/i386-redhat-linux6E/4.4.7/../../../../include/c++/4.4.7/istream:188: note: std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(long unsigned int&) [with _CharT = char, _Traits = std::char_traits]
/usr/lib/gcc/i386-redhat-linux6E/4.4.7/../../../../include/c++/4.4.7/istream:193: note: std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(long long int&) [with _CharT = char, _Traits = std::char_traits]
/usr/lib/gcc/i386-redhat-linux6E/4.4.7/../../../../include/c++/4.4.7/istream:197: note: std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(long long unsigned int&) [with _CharT = char, _Traits = std::char_traits]
/usr/lib/gcc/i386-redhat-linux6E/4.4.7/../../../../include/c++/4.4.7/istream:202: note: std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(float&) [with _CharT = char, _Traits = std::char_traits]
/usr/lib/gcc/i386-redhat-linux6E/4.4.7/../../../../include/c++/4.4.7/istream:206: note: std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(double&) [with _CharT = char, _Traits = std::char_traits]
/usr/lib/gcc/i386-redhat-linux6E/4.4.7/../../../../include/c++/4.4.7/istream:210: note: std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(long double&) [with _CharT = char, _Traits = std::char_traits]
/usr/lib/gcc/i386-redhat-linux6E/4.4.7/../../../../include/c++/4.4.7/istream:214: note: std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(void*&) [with _CharT = char, _Traits = std::char_traits]
/usr/lib/gcc/i386-redhat-linux6E/4.4.7/../../../../include/c++/4.4.7/istream:238: note: std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(std::basic_streambuf<_CharT, _Traits>*) [with _CharT = char, _Traits = std::char_traits]
/tmp/judge/POD_{87634489-7147-4a0b-bf89-13d0f24b9c9f}/solution.cpp:22: error: invalid operands of types ‘int [(((unsigned int)(((int)ile_liczb) + -0x000000001)) + 1)]’ and ‘int’ to binary ‘operator/’
/tmp/judge/POD_{87634489-7147-4a0b-bf89-13d0f24b9c9f}/solution.cpp:24: error: invalid operands of types ‘int [(((unsigned int)(((int)ile_liczb) + -0x000000001)) + 1)]’ and ‘int’ to binary ‘operator%’ |
|
Tomek_z_W11 |
» 2014-10-30 12:52:49 Wowowowow.
Skopiowales dokladnie moj kod? wlacznie z tym "using namespace std"? |
|
mati1995g Temat założony przez niniejszego użytkownika |
» 2014-10-30 13:04:53 Tak skopiowałem dokładanie kod, lecz chyba problem leży w tym, że oni na serwerze w danych wejściowych mają same liczby z których się wyznacza dzielniki, a u ciebie trzeba ich ilość wprowadzić ręcznie. |
|
Monika90 |
» 2014-10-30 13:09:28 Tomek, kod dajemy między znaczniki [cpp][/cpp] wyedytuj swój post. |
|
Tomek_z_W11 |
» 2014-10-30 13:16:45 Masz napisac taki program nie wiedzac ile liczb wejsciowych moze wejsc?
Toz to niemozliwe... Jak program ma przewidziec ilosc danych wejsciowych?
Jedyna rzecz jaka mi przychodzi na mysl to zmienic troche kod, nie wiem czy to zadziala, bo zalozymy, ze wejdzie maksymalna ilosc liczb, czyli 60002.
Nie mowiac o tym, ze na tym serwerze, program obslugujacy to wszystko moze dzialac w ten sposob, ze najpierw wrzuca wszystkie dane, a potem oczekuje na odpowiedz, w tym momencie moj program pobiera dane i od razu wyrzuca odpowiedz:
#include<iostream>
using namespace std;
int main()
{
int i, j, licznik=0; //do petli, do zliczania dzielnikow
int tablica_liczb[60002]; //tablica z iloscia elementow rowna maksymalnej ilosci jaka moze wejsc
for(i=0; i<60002; i++) //petla idaca po wszystkich komorkach tablicy (od zera ro rozmiaru tablicy)
{
cin >> tablica_liczb; //pobranie i-tej liczby
for(j=1; j<=tablica_liczb/2; j++) //petla potrzebna do wylapania wszystkich dzielnikow, idziemy od 1, bo przez 0 nie mozna
{ //dzielic, do tab_liczb/2, bo nie ma potrzeby isc do konca liczby, tzn:
if(tablica_liczb%j==0) //majac liczbe 18, nie znajdziemy dzielnika wiekszego od 9, oprocz 18, ten przypadek
{ //zostal uwzgledniony.
licznik++; //zliczanie dzielnikow
}
}
licznik++; //uwzglednienie przypadku, ze kazda liczba jest podzielna przez sama siebie
cout << licznik << endl;
licznik=0;
}
return 0;
} |
|
mati1995g Temat założony przez niniejszego użytkownika |
» 2014-10-30 13:27:02 "Wejście
W kolejnych wierszach standardowego wejścia zapisano po jednej liczbie naturalnej L do sprawdzenia (2≤L≤10000000).
Liczba wierszy nie przekracza 60002.W ostatnim wierszu zapisana jest wartość 0,dla której nie dokonujemy obliczeń.
Wyjście
W kolejnych wierszach standardowego wyjścia zapisz obliczoną liczbę podzielników liczby wczytanej z wejścia,zachowując kolejność wczytywania."
Oto treść zadania, wnioskując z niej nie masz podanej ilości liczb wejściowych, tylko że ostatnia to 0, chyba, że się mylę...
Błąd kompilacji
/tmp/judge/POD_{496ad7dc-8179-4af9-afe6-9970d0a7bce6}/solution.cpp: In function ‘int main()’:
/tmp/judge/POD_{496ad7dc-8179-4af9-afe6-9970d0a7bce6}/solution.cpp:13: error: no match for ‘operator>>’ in ‘std::cin >> tablica_liczb’
/usr/lib/gcc/i386-redhat-linux6E/4.4.7/../../../../include/c++/4.4.7/istream:119: note: candidates are: std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(std::basic_istream<_CharT, _Traits>& (*)(std::basic_istream<_CharT, _Traits>&)) [with _CharT = char, _Traits = std::char_traits]
/usr/lib/gcc/i386-redhat-linux6E/4.4.7/../../../../include/c++/4.4.7/istream:123: note: std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(std::basic_ios<_CharT, _Traits>& (*)(std::basic_ios<_CharT, _Traits>&)) [with _CharT = char, _Traits = std::char_traits]
/usr/lib/gcc/i386-redhat-linux6E/4.4.7/../../../../include/c++/4.4.7/istream:130: note: std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(std::ios_base& (*)(std::ios_base&)) [with _CharT = char, _Traits = std::char_traits]
/usr/lib/gcc/i386-redhat-linux6E/4.4.7/../../../../include/c++/4.4.7/istream:166: note: std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(bool&) [with _CharT = char, _Traits = std::char_traits]
/usr/lib/gcc/i386-redhat-linux6E/4.4.7/../../../../include/c++/4.4.7/istream:170: note: std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(short int&) [with _CharT = char, _Traits = std::char_traits]
/usr/lib/gcc/i386-redhat-linux6E/4.4.7/../../../../include/c++/4.4.7/istream:173: note: std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(short unsigned int&) [with _CharT = char, _Traits = std::char_traits]
/usr/lib/gcc/i386-redhat-linux6E/4.4.7/../../../../include/c++/4.4.7/istream:177: note: std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(int&) [with _CharT = char, _Traits = std::char_traits]
/usr/lib/gcc/i386-redhat-linux6E/4.4.7/../../../../include/c++/4.4.7/istream:180: note: std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(unsigned int&) [with _CharT = char, _Traits = std::char_traits]
/usr/lib/gcc/i386-redhat-linux6E/4.4.7/../../../../include/c++/4.4.7/istream:184: note: std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(long int&) [with _CharT = char, _Traits = std::char_traits]
/usr/lib/gcc/i386-redhat-linux6E/4.4.7/../../../../include/c++/4.4.7/istream:188: note: std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(long unsigned int&) [with _CharT = char, _Traits = std::char_traits]
/usr/lib/gcc/i386-redhat-linux6E/4.4.7/../../../../include/c++/4.4.7/istream:193: note: std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(long long int&) [with _CharT = char, _Traits = std::char_traits]
/usr/lib/gcc/i386-redhat-linux6E/4.4.7/../../../../include/c++/4.4.7/istream:197: note: std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(long long unsigned int&) [with _CharT = char, _Traits = std::char_traits]
/usr/lib/gcc/i386-redhat-linux6E/4.4.7/../../../../include/c++/4.4.7/istream:202: note: std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(float&) [with _CharT = char, _Traits = std::char_traits]
/usr/lib/gcc/i386-redhat-linux6E/4.4.7/../../../../include/c++/4.4.7/istream:206: note: std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(double&) [with _CharT = char, _Traits = std::char_traits]
/usr/lib/gcc/i386-redhat-linux6E/4.4.7/../../../../include/c++/4.4.7/istream:210: note: std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(long double&) [with _CharT = char, _Traits = std::char_traits]
/usr/lib/gcc/i386-redhat-linux6E/4.4.7/../../../../include/c++/4.4.7/istream:214: note: std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(void*&) [with _CharT = char, _Traits = std::char_traits]
/usr/lib/gcc/i386-redhat-linux6E/4.4.7/../../../../include/c++/4.4.7/istream:238: note: std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(std::basic_streambuf<_CharT, _Traits>*) [with _CharT = char, _Traits = std::char_traits]
/tmp/judge/POD_{496ad7dc-8179-4af9-afe6-9970d0a7bce6}/solution.cpp:14: error: invalid operands of types ‘int [60002]’ and ‘int’ to binary ‘operator/’
/tmp/judge/POD_{496ad7dc-8179-4af9-afe6-9970d0a7bce6}/solution.cpp:16: error: invalid operands of types ‘int [60002]’ and ‘int’ to binary ‘operator%’
i kolejny błąd kompilacji po wrzuceniu twojego kodu. |
|
| « 1 » 2 3 |