[dzimen]

#programowanie #cpp

Witam mam pytanie jak przekształcić sito Eratostenesa, liczby pierwsze i rozkład na czynniki pierwsze z funkcji iteracyjnej na funkcję rekurencyjną? Jak będzie potrzebny kod to podeślę na pastebinie. Liczę na pomoc.

[dzimen]

@KuszacaWoda: szukałem już w internecie i wszystko jest przez iterację. Nigdzie nie ma z użyciem rekurencji na te funkcje.

[g.....i]

@dzimen: zamień sobie sumowanie liczb całkowitych od 1 do n z pętli na rekurencje to zrozumiesz ze rekurencja jest trywialna i pierwotna w stosunku do pętli.

[dzimen]

@gozwei: no tak ale jeżeli mam pętle w liczba pierwszych for(int =2; i*i<=n;i++) to jak to zamienić na rekurencję?

[P.....3]

@dzimen: Przecież ci to zrobiłem wczoraj, wtf?...

[dzimen]

@Porana123: ale to tak nie chce działać

[P.....3]

@dzimen: No to może powiesz co ci nie działa?

[d.....t]

@dzimen: @Porana123: Moim zdaniem rozwiązanie Porana jest poprawne,

bool isPrime(long n, long divider) {
if (n == 2)
return true;
if (n % 2 == 0)
return false;
if (divider <= 1)
return true;
if (n%divider != 0)
return isPrime(n, divider - 1);
return false;
}

kluczem w przypadku tego rozwiazania jest dobór maksymalnego dzielnika tj. np. dla 10 będzie to 3, więc przykładowe wywołanie to: isPrime(10,3)

[P.....3]

@drift: No ta, trzeba podać dobry dzielnik wiadomo, i jeszcze uwzględnić przypadek z jedynką, pisałem to na szybko. Generalnie idea taka żeby to po prostu opakować w funkcję z tylko jednym argumentem czyli liczbą która chcemy sprawdzić, i ta funkcja zajmie się okresleniem maksymalnego dzielnika i wywoła właśnie tą. Najlepiej w tej funkcji z 1 argumentem uwzględnić własnie liczby parzyste i jedynke od razu, żeby nie wchodziło w tą drugą nawet.

[dzimen]

@Porana123: @drift: No ok, ale nie działa całkowicie prawidłowo
bool isPrime(int n, int x) {
if(n<2)
return true;
if(n % 2 == 0)
return false;
if(x <= 1)
return true;
if(n % x != 0)
return isPrime(n, x - 1);
return false;
}

Wywołuje to w switch'u tak:
int n;
cout<<"Podaj liczbe: ";
cin>>n;
if(isPrime(n,x))
cout<<"Liczba "<<n<<" jest pierwsza"<<endl;
else
cout<<"Liczba "<<n<<" nie jest pierwsza"<<endl;

I teraz wygląda tak ze

[P.....3]

@dzimen: Tam na początku nie ma być <2 tylko ==2, czym jest x u ciebie w wywołaniu? Jak nie chce ci się bawić z szukaniem odpowiednego dzielnika to wywołuj po prostu isPrime(n,n/2).

[morsisko]

@dzimen: Przeanalizuj to, i będziesz wiedział czemu. Wykaż trochę własnej inicjatywy.

[dzimen]

@Porana123: x to twój devider

[P.....3]

@dzimen: No ale jaka wartość...

[dzimen]

@Porana123: a da się jakoś bez tego divider/x?

[P.....3]

@dzimen: Wszystko się da, tylko to będzie bardziej skomplikowane, nieintuicyjne i prawdopodobnie głupie, jeśli samo robienie sprawdzania liczb pierwszych rekurencyjnie nie jest głupie, no ale to zapewne jakiś homework. Po prostu zrób

if(isPrime(n,n/2))
cout<<"Liczba "<<n<<" jest pierwsza"<<endl;
else
cout<<"Liczba "<<n<<" nie jest pierwsza"<<endl;

[dzimen]

@Porana123: zostało mi teraz sito Eratostenesa i rozkład na czynniki pierwsze ale to już dla mnie czarna magia. Bo tam są tablice i nwm jak można tablicę na rekurencję zamienić i wgl...

[P.....3]

@dzimen: Przecież to jest jeszcze prostsze niż tamto, wypełniasz tablice od 2 indeksu liczbami od 2 czyli array[2]=2, array[3]=3 i tak do jakiegoś n, potem wywołujesz sito(n, 2), robisz w środku pętle for i=2 to n do array[i]=0 (oczywiście do i nie dodajesz 1 tylko to co w drugim argumencie, czyli 2) i potem sito(n, 3) i tak dopóki 2 argument nie będzie większy od pierwiastka z n (to trzeba sprawdzić

[dzimen]

@Porana123: chce mi się, ale po prostu nwm jak się zabrać za to... Tym bardziej ze iteracyjne sito i rozkład jest banalny i wydajniejszy niż rekurencyjny...