[C++] Sito Eratostenesa, szukanie dzielników liczby

agggnes
Użytkownik
Użytkownik
Posty: 87
Rejestracja: 21 gru 2011, o 21:27
Płeć: Kobieta
Podziękował: 18 razy

[C++] Sito Eratostenesa, szukanie dzielników liczby

Post autor: agggnes »

napisz program, który metodą sita Eratostenesa wyznaczy wszystkie dzielniki liczby \(\displaystyle{ 1600}\).

Proszę o pomoc, wiem na czym polega ta metoda, ale jak ją zastosować do tego zad?
Ostatnio zmieniony 28 lut 2012, o 18:51 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
anna_
Użytkownik
Użytkownik
Posty: 16323
Rejestracja: 26 lis 2008, o 20:14
Płeć: Kobieta
Podziękował: 35 razy
Pomógł: 3245 razy

[C++] Sito Eratostenesa, szukanie dzielników liczby

Post autor: anna_ »

Sito Eratostenesa służy do wyszukiwania liczb pierwszych.
Dobrze spisałaś treść?
agggnes
Użytkownik
Użytkownik
Posty: 87
Rejestracja: 21 gru 2011, o 21:27
Płeć: Kobieta
Podziękował: 18 razy

[C++] Sito Eratostenesa, szukanie dzielników liczby

Post autor: agggnes »

cały problem polega na tym, ze tak:/

wiem o co chodzi w tej metodzie i też wydawało mi się, że tego zadania się nie da tak rozwiązać, ale myslałam że może po prostu nie mogę na nie wpaść...
anna_
Użytkownik
Użytkownik
Posty: 16323
Rejestracja: 26 lis 2008, o 20:14
Płeć: Kobieta
Podziękował: 35 razy
Pomógł: 3245 razy

[C++] Sito Eratostenesa, szukanie dzielników liczby

Post autor: anna_ »

Na programowaniu niestety się nie znam, ale może w takim chodzi o sprawdzanie kolejno podzielności liczby 1600 przez kolejne liczby od 1 do 1600.
adambak
Użytkownik
Użytkownik
Posty: 1272
Rejestracja: 8 sty 2011, o 18:18
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 295 razy
Pomógł: 115 razy

[C++] Sito Eratostenesa, szukanie dzielników liczby

Post autor: adambak »

a może chodziło o wszystkie dzielniki pierwsze? wtedy to by miało jakiś sens..
sito tworzymy z tablicy intów, \(\displaystyle{ \text{sito=i}}\) wtedy i tylko wtedy gdy \(\displaystyle{ \text{i}}\) jest liczbą pierwszą, a w przeciwnym wypadku \(\displaystyle{ \text{sito= najmniejszy pierwszy dzielnik i}}\), czyli drobna modyfikacja sita.. w ten sposób tworzy nam się taka tabelka dzielenia i wykonując kilka dzieleń w pętli while mamy rozkład liczby na czynniki pierwsze..
Grzesio_
Użytkownik
Użytkownik
Posty: 44
Rejestracja: 23 gru 2011, o 22:59
Płeć: Mężczyzna
Lokalizacja: Polska
Pomógł: 3 razy

[C++] Sito Eratostenesa, szukanie dzielników liczby

Post autor: Grzesio_ »

nie musimy sprawdzać podzielności przez wszystkie liczby nie większe od pierwiastka z N,
ale tylko przez liczby pierwsze nie większe od tego pierwiastka.
jeżeli w dwu tablicach: p[], w[] mamy rozkład N na czynniki pierwsze \(\displaystyle{ N=\prod_{i=0}^{k-1}p^{w}}\) to wołając pisz(k, 0, 1) uzyskamy wszystkie dzielniki N
a funkcja ta może wyglądać np. tak:

Kod: Zaznacz cały

void pisz(int k, int n, int d){
        if( n<k ) 
                for( int i=0; i<=w[n]; i++ ) {
                        pisz(k, n+1, d);
                        d *=p[n]; }
        else 
                cout << d << " ";
}
*jeżeli wyszukać sitem wszystkie pierwsze aż do N, wtedy dzielniki pierwsze N wyskoczą przy okazji
i (prawie) żadne dzielenie nie pójdzie na darmo
ODPOWIEDZ