» Forum » Programowanie » [C, C++] Szukam pomocy

[C++] Sito Eratostenesa

Ostatnio zmodyfikowano 2010-09-19 11:41

lenrokskate

Temat założony przez niniejszego użytkownika

» 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(); //czyscimy liste
int max = ui->spinBox->value(); //pobieramy z konstrolki liczbę - wypisujemy liczby pierwsze mniejsze od niej
vector < int > tab( max ); //tworzymy vector na liczby pierwsze
for( int i = 0; i < max; i++ ) tab[ i ] = i + 1; //wypelniamy go

tab.erase( tab.begin() ); //usuwamy liczbe 1 bo nie jest lp (liczba pierwsza)
int ind = 1;;
for( int d = 2; d < tab.size(); )
{
for( int i = 0; i < tab.size(); i++ ) //usuwamy wielokrotnosci liczby d wieksze od niej
{
if( tab[ i ] % d == 0 ) tab.erase( tab.begin() += i );

}
d = tab[ ind ]; //bierzemy pierwsza nie usunieta liczbe
ind++; //powiekszamy indeks aby potem pobrac kolejna nieskreslona liczbe
}
for( int i = 0; i < tab.size(); i++ ) ui->listWidget->addItem( QString::number( tab[ i ] ) ); //wypisujemy wszystkie liczby z vectora

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++ ) // przeszukuj liczby od 2 do sqrt(n), 0 i 1 nie są liczbami pierwszymi
{
if( numbersTable[ i ] == true ) // jeżeli dana liczb jest już wykreślona
   continue; // to przejdź do kolejnej

for( int j = 2 * i; j <= n; j += i ) // przejdź od liczby 2 * i do n przesuwając się o i
   numbersTable[ j ] = true; // i każdą z nich usuwaj ze zbioru

}
for( int i = 2; i <= n; i++ ) // przeszukaj liczby od 2 do n
if( numbersTable[ i ] == false ) // jeśli liczba nie została usunięta ze zbioru
   ui->listWidget->addItem( QString::number( i ) ); // to ją wypisz

wypisuje dobrze do czasu liczby 25 (zle)

P-22099

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).

P-22105

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

P-22107

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 );

}

P-22108

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?

P-22109

malan

» 2010-09-18 19:00:59

tab.begin() += i

?
Poprawnie:

tab.begin() + i

P-22110

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;
}
} //petla główna
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

P-22118

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 :)

P-22119

« 1 » 2

Strona 1 z 2

Następna strona

» Forum » Programowanie » [C, C++] Szukam pomocy