Evo neki hint, vezano za oblik 2^k - 1.

Posmatramo neki broj x; kako ustanoviti da li spada u trazenu grupu? Ja bih pokusao ovako. Dodam 1 (jedinicu) na x i dobijem x1, i zatim udjem u petlju:



Na izlazu iz petlje, ako je x1 = 0, tada je polazni broj x upravo oblika 2^k - 1. Da li je Mersenov broj, e to moras da proveris da li je i prost .

Pozz

Hvala puno

Uh... ne zahvaljuj prebrzo.

Sad sam uvideo gresku u uslovu petlje(na brzinu je radjeno), kod zapravo treba da ide ovako:



Dakle, ako je na izlazu iz petlje x1 == 1, tada je polazni broj x trazenog oblika 2^k - 1. Jer za x1 == 1, nikad se nece pozvati x1 >>= 1 (zbog modulo uslova), i x1 nikad nece doseci 0 (nulu).

Pozz

Da li je broj stepen broja 2 najlakše proveriti tako što mu prebrojiš 1 bitove. Ako ima jedan 1 bit, onda jeste, inače nije. :)

BTW nije li brže da se mersenovi brojevi traže tako što se redom proveravaju brojevi oblika 2^k-1 na prostoću, nego da se proveravaju redom prosti brojevi na to da li zadovoljavaju zadati oblik? :)

Jos je lakse da uradis bitwise I sa vrednoscu umanjenom za 1. Ukoliko je rezultat 0, radi se o stepenu broja dva.

Specijalni slucaj je vrednost 0.

Primer n = 16 = 0b10000

n & (n - 1) = 0b10000 & 0b1111 = 0

Au, sjajno razmisljanje .

Medjutim, trazi se dijagram toka - pretpostavljam da se trazi nesto smisleno, a ne 'magic code' (mada, koristio sam '>>'). Sta kad bi trazeni oblik broja bio n^k - 1 (n umesto 2)?
Onda bi valjda donji kod radio (opet je int x1 = x + 1):



Drzi li ovo vodu: ako je po izlasku iz petlje x1 == 1, pocetni x1 je stepen broja n?

Pozz


<sub>[Ovu poruku je menjao Rapaic Rajko dana 18.02.2016. u 13:30 GMT+1]

[Ovu poruku je menjao Rapaic Rajko dana 18.02.2016. u 13:30 GMT+1]</sub>