liczby pierwsze Opcje

[invx]

potrzebuje znalezc wszytskie iliczby pirwsze, z podaneo zakresu, nie uzywajac tablic, jedynie zwykle zmienne warunek IF, i petle FOR,
mialem pomysl, zeby sprawdzic czy poczatkowa liczba jest mniejsza od 10 czy nie, jak tak to spawdzam czy nie jest ona rowna 1 3 5 7 9, a jesli powyzej czy ma reszte jak sie ja podzieli przez 2 3 4 5 6 7 8 9 czy nie, i w zaleznosci od tego alba ja wyswitlam albo nie

co o tym sadzicie ?

[rogrog]

invx przerabia algorytmike

poszukaj o czymś takim jak sito Eratostenesa

i najlepiej kup sobie jakąś książkę o algorytmach (np. M. Sysło, Algorytmy - to jest od podstaw, chociaż dosyć stara książka)

[invx]

boki zrywac

wiem ze jes takie sito, bo takie mielismy temat lekcji
pytam co o tym sadzicie co napisalem bo jak dobre koduje to.

[dr_bonzo]

Zly algorytm: a co dla liczby 221 (12 x 17)? jest przeciez pierwsza? a nie jest podzielna przez 2, 3, 5, 7
(9 nie jest pierwsza!!)
1 - nie jest liczba pierwsza ani ta druga (zlozona?)

Najprostszy algorytm (najwolniejszy):
N -- sprawdzana liczba
loopujesz przez liczby od 2 do floor( N/2 )
i sprawdzasz czy N jest podzielna przez ktorakolwiek z nich -- jesli tak to nie jest pierwsza.

[FiDO]

Najprostszy algorytm (najwolniejszy):
N -- sprawdzana liczba
loopujesz przez liczby od 2 do floor( N/2 )
i sprawdzasz czy N jest podzielna przez ktorakolwiek z nich -- jesli tak to nie jest pierwsza.

Mozna to troche zoptymalizowac i szukac do floor(sqrt(N)) a nie do N/2.

[invx]

to mui byc bez funkcji ...

[dr_bonzo]

No to rzutuj (najwyzej zrobisz kilka iteracji za duzo):
(int)( N / 2)

[rogrog]

hmm to nie kumam po co chcesz robic nieoptymalnym algorytmem i sie pytasz o cos takiego...
zreszta myslalem ze mozesz o tym algorytmie nie wiedziec no ale jak tak to sorry

Ten post edytował rogrog 6.03.2005, 21:08:57

[dr_bonzo]

Juz nie pierwszy raz invx dostaje takie zadania (posortowanie liczb tylko za pomoca if-ow)

[TomASS]

Zwykle algorytmy dokładne są dosyć wolne, a złożonoś obliczeniowa duża. Radzę Ci, abyś zapoznał się z algorytmami przybliżonymi np. algorytmem Monte Carlo do obliczania liczb pierwszych. Jeśli kogoś interesuje ten temat, to bardzo chętnie mogę przybliżyć.

Pozdrawiam serdecznie

[orson]

witam ...

@TomASS hmm ... a mnie sie wydaje ze to ma nie byc wydajne tylko wg polecenia w zadaniu domowym

pozdrawiam

[NuLL]

A jaki ma być zasięg tych liczb- mozna to zrobic w dwoch petlach:)

Aby sprawdzizc czy danan liczba jest pierwsza poporostu dzielisz modulo przez wszystkie liczby mnijesze od niej - i jesli reszta rowna sie zero z ktores z nich to ona nie jest pierwsza i na odwrot - jesli dana liczba dze\ieli wsie przez wszystkie mniejsze od sieibe dajac reszte to jest to liczba pierwsza

[hawk]

@rogrog:
Sito Erastotenesa właśnie wykorzystuje tablicę, wiec odpada.

@invx:
Jeżeli nie możesz wykorzystać tablicy, a zakres poszukiwania jest dowolny, to niestety nie da się zrobić algorytmu z "pamięcią". Czyli dla każdej liczby poszukiwania trzeba zacząć od nowa.