[ bubamara997 @ 13.02.2016. 11:51 ] @
Imam problem oko zadatka.. Molim pomoc ako moze..
Zadatak glasi:
Dijagramom toka predstaviti algoritam koji ucitava broj n, a zatim ispisuje prvih n Mersenovih prostih brojeva. Mersenovi prosti brojevi su prosti brojevi oblika 2^k-1, k>=2. Prirodan broj veci od jedan je prost ako je djeljiv samo sa jedan i samim sobom.

Znam da je zadatak lagan ali problem mi je nastao kod 2^k
[ Rapaic Rajko @ 15.02.2016. 08:07 ] @
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:

Code:

  while ((x1 > 0) && (x1 % 2) == 0) // x1 je int, podrazumevano
    x1 >>= 1;                           // shift-ujemo ga u desno za 1 bit, ekvivalentan kod je: x1 = x1 / 2; 


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
[ bubamara997 @ 17.02.2016. 12:23 ] @
Hvala puno
[ Rapaic Rajko @ 17.02.2016. 14:09 ] @
Uh... ne zahvaljuj prebrzo.

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

Code:

  while ((x1 > 1) && (x1 % 2) == 0)
    x1 >>= 1; 


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
[ jablan @ 17.02.2016. 16:08 ] @
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? :)
[ scoolptor @ 17.02.2016. 16:28 ] @
Citat:
Da li je broj stepen broja 2 najlakše proveriti tako što mu prebrojiš 1 bitove


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
[ Rapaic Rajko @ 18.02.2016. 07:35 ] @
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):

Code:

  while ((x1 > 1) && (x1 % n) == 0)
    x1 /= n;


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

Pozz


[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]