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?
[C++] Sito Eratostenesa, szukanie dzielników liczby
[C++] Sito Eratostenesa, szukanie dzielników liczby
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ść...
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ść...
-
- 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
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.
-
- 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
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..
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..
-
- 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
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:
*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
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 << " ";
}
i (prawie) żadne dzielenie nie pójdzie na darmo