[C++] Sito Eratostenesa
Ostatnio zmodyfikowano 2010-09-19 11:41
lenrokskate Temat założony przez niniejszego użytkownika |
[C++] Sito Eratostenesa » 2010-09-18 14:00:34 Mam nadzieję że wszyscy wiedzą co to jest... Oto kod (napisany w Qt ale opisałem co i jak więc to nie ma znaczenia) ui->listWidget->clear(); int max = ui->spinBox->value(); vector < int > tab( max ); for( int i = 0; i < max; i++ ) tab[ i ] = i + 1;
tab.erase( tab.begin() ); int ind = 1;; for( int d = 2; d < tab.size(); ) { for( int i = 0; i < tab.size(); i++ ) { if( tab[ i ] % d == 0 ) tab.erase( tab.begin() += i ); } d = tab[ ind ]; ind++; } for( int i = 0; i < tab.size(); i++ ) ui->listWidget->addItem( QString::number( tab[ i ] ) );
teraz odpaliłem program, wpisałem 41 jako max i wypisało liczby: 3-ok //nie ma 5 7-ok 11-ok //niema 13 17-ok 19-ok 21-error!!! ślęcze już nad tym razem jakieś 5h i nic nie wymyśliłem - jak naprawię jedno to się rąbie drugie... #edit wykombinowałem coś takiego: ui->listWidget->clear(); int max = ui->spinBox->value(); vector < int > tab( max ); for( int i = 0; i < max; i++ ) tab[ i ] = i + 1;
tab.erase( tab.begin() ); int ind = 1; for( int d = 2; d < tab.size(); ) { for( int i = 0; i < tab.size(); i++ ) { if( tab[ i ] % d == 0 && tab[ 1 ] > d ) tab.erase( tab.begin() += i ); } d = tab[ ind ]; ind++; } for( int i = 0; i < tab.size(); i++ ) ui->listWidget->addItem( QString::number( tab[ i ] ) );
i dalej nie działa, wypisuje po prostu kolejne liczby +2 od poprzedniej, czyli 3-5-7-9-11-13-15 itp.. #edit2 znalazłem jakiś inny algorytm tutaj ale dziwi mnie czemu mój nie działa dodatkowo ten kod z wikipedii też nie działa do końca poprawnie: ui->listWidget->clear(); int n = ui->spinBox->value(); bool numbersTable[ n + 1 ]; for( int i = 2; i * i <= n; i++ ) { if( numbersTable[ i ] == true ) continue; for( int j = 2 * i; j <= n; j += i ) numbersTable[ j ] = true; } for( int i = 2; i <= n; i++ ) if( numbersTable[ i ] == false ) ui->listWidget->addItem( QString::number( i ) );
wypisuje dobrze do czasu liczby 25 (zle) |
|
DejaVu |
» 2010-09-18 16:01:25 Cóż, zapewne masz błąd w algorytmie skoro źle działa... sam znalazłeś sobie poprawne rozwiązanie, więc porównaj sobie działania obu algorytmów na kartce lub wypisz listę operacji w konsoli (dla obu algorytmów). |
|
lenrokskate Temat założony przez niniejszego użytkownika |
» 2010-09-18 16:05:46 ślęczałem już z kartką dość na tym i wg. moich wyliczeń powinno działać dobrze... tylko teraz czemu nawet algorytm z wiki nie działa choć jest mniej skomplikowany od mojego i wygląda na to że także lepiej działa, tymczasem nie działa ani jedno ani drugie...
kod skopiowany z wikipedii działa idealnie w konsoli, a tutaj podmieniłem tylko 2 rzeczy - pobieranie max. liczby i wyświetlanie liczb pierwszych, czyli tutaj jest błąd, tylko dalej nie wiem gdzie...
#edit zauważyłem, że gdy max. liczbę mam w const int znanym przy kompilacji to program działa, natomiast jeśli pobieram tą liczbę poprzez cin to wypisuje jakieś głupoty |
|
Elaine |
» 2010-09-18 16:19:23 a tutaj podmieniłem tylko 2 rzeczy |
Trzy - tablicę alokujesz na stosie (dla większych n prosisz się o problemy; może pora zapomnieć o głupkowatych rozszerzeniach GCC i użyć vectora, jak to robi cały cywilizowany świat?) i zapominasz o jej inicjalizacji.
Ten kod działa: #include <cstdio> #include <vector> using namespace std;
int main() { unsigned int max; scanf( "%u", & max ); vector < unsigned char > numbersTable( max + 1, 0 ); for( unsigned int i = 2; i * i <= max; ++i ) { if( numbersTable[ i ] != 0 ) continue; for( unsigned int j = i * 2; j <= max; j += i ) numbersTable[ j ] = 1; } for( unsigned int i = 2; i <= max; ++i ) if( numbersTable[ i ] == 0 ) printf( "%u\n", i ); } |
|
lenrokskate Temat założony przez niniejszego użytkownika |
» 2010-09-18 18:37:33 dzięki Iname, działa :)
zostało mi tylko jeszcze 1 pytanie - dlaczego sposób z usuwaniem elementu z vectora nie działa? |
|
malan |
» 2010-09-18 19:00:59 tab.begin() += i ? Poprawnie: tab.begin() + i . |
|
elradziu |
» 2010-09-19 11:30:07 #include <cstdlib> #include <iostream>
using namespace std;
int main( int argc, char * argv[] ) { int n; cin >> n; cout << endl; for( int i = 3; i <= n; i++ ) { for( int j = 2; j < i; j++ ) { if(( i % j ) == 0 ) break; cout << i << endl; } } system( "PAUSE" ); return EXIT_SUCCESS; }
musisz tylko popracować nad tym żeby kilka razy nie wyświelało tej samej liczby. Mi się nie chce. Sprawdzałem tylko do 41; :p |
|
lenrokskate Temat założony przez niniejszego użytkownika |
» 2010-09-19 11:32:36 dzięki El Radziu ale już mam działające rozwiązanie :) |
|
« 1 » 2 |